lower_bound
upper_bound
equal_range
they perform binary search on sorted list of data and return either first index where you could insert object without violating ordering, last index, or both indices.
look them up in an stl reference
![:)](./images/smilies/icon_smile.gif)
Moderator: Board moderators
Code: Select all
#include <iostream>
#include <list>
#include <deque>
#include <stdio.h>
using std::cin;
using std::cout;
using std::endl;
#include <map>
#include <string>
std::deque<string> dictionary;
std::map<string, std::deque<string>, std::less<string> > hash;
// Searches if theres a way to get in string sEnd, starting from string sStart
int procuraDoublet( string sStart, string sEnd )
{
// If strings have different sizes they cant be doublets
if ( sStart.length() != sEnd.length() )
return 0;
// if start string doesnt have any doublet, so there no way
// to reach end string
if ( hash[sStart].front() == "empty" )
return 0;
// Otherwise, verify if theres a doublet
for ( int i = 0; i < hash[sStart].size(); ++i )
if ( hash[sStart][i] == sEnd )
{
cout << hash[sStart][i] << endl;
return 1;
}
// if there wasnt any direct doublet, try second order doublet and so on
for ( int i = 0; i < hash[sStart].size(); ++i )
if ( procuraDoublet( hash[sStart][i], sEnd ) )
{
cout << hash[sStart][i] << endl;
return 1;
}
return 0;
}
int doublet( string s1, string s2)
{
if ( s1.length() != s2.length() )
return 0;
int nDiff = 0;
for ( int i = 0; i < s1.length(); i++ )
if ( s1[i] != s2[i] )
{
nDiff++;
if ( nDiff == 2 )
return 0;
}
return 1;
}
int main()
{
char entrada[18];
int dictSize = 0;
std::list<string> d;
while (true )
{
cin.getline( entrada, 17, '\n' );
if ( entrada[0] == '\0')
break;
d.push_back( entrada );
if ( hash[entrada].empty() )
hash[entrada].push_back("empty");
}
d.unique();
dictSize = d.size();
while ( !d.empty() )
{
dictionary.push_back(d.front() );
d.pop_front();
}
for ( int i = 0; i < dictSize; i++ )
{
if ( hash[dictionary[i]].front() == "empty" )
hash[dictionary[i]].pop_front();
for ( int j = 0; j < dictSize; j++ )
if ( i != j )
if ( doublet(dictionary[i], dictionary[j]) )
hash[dictionary[i]].push_back(dictionary[j]);
}
string s1, s2;
while (cin >> s1 >> s2 )
{
if (hash[s1].empty() )
hash[s1].push_back("empty");
if (hash[s2].empty() )
hash[s2].push_back("empty");
if (procuraDoublet( s2, s1 ) == 0 )
cout << "No solution" << endl;
else
cout << s2 << endl;
cout << endl;
}
}
The 28s submission was submitted before server upgrade(about 2-3 years ago), at that time the server is slower so a larger time limit is given.hiro wrote:Hi everybody...
Im having some trouble submitting Doublets...
i always get TL with 10,39 s, but in the ranking lista there's a submission that took about 28s...
Code: Select all
#include <iostream>
#include <queue>
#include <stdlib.h>
#include <string>
#define maxV 25148
using namespace std;
struct node
{
int v;
struct node *next;
};
int V;
struct node *adj[maxV], *z;
char dic[maxV][20];
int val[maxV];
int path[maxV];
int comp(const void *a, const void *b)
{
return(strcmp((char *)a,(char *)b));
}
int bsearch(char a[])
{
int l = 0, r = V, x, t;
while(r >= l) {
x = (l + r)/2;
t = comp( a, dic[x]);
if(t == 0) return x;
else if(t < 0) r = x - 1;
else l = x + 1;
}
return -1;
}
int main(void)
{
struct node *t;
int i = 0, j, k, l, len;
char tmp[18];
while(true) {
cin.getline( dic[i], 17, '\n');
if ( dic[i][0] == '\0')
break;
i++;
}
V = i - 1;
z = new node; z->next = z;
for( i = 0; i <= V; i++) {
adj[i] = z;
adj[i]->v = i;
}
qsort(dic,V + 1,sizeof(dic[0]),comp); //sort the words
for( i = 0; i <= V; i++) {
len = strlen(dic[i])-1;
for( j = 0; j <= len; j++) {
for( k = 0; k <= 25; k++) {
if(dic[i][j] != (char)('a'+ k)) { //find the Doublets
strcpy( tmp, dic[i]);
tmp[j] = (char)('a' + k);
l = bsearch(tmp);
if(l != -1) {
t = new node;
t->v = l; t->next = adj[i]; adj[i] = t;
}
}
}
}
}
char a[18],b[18];
bool success;
int sur, des;
queue<int> q;
while(cin>>a>>b)
{
memset(val,-1,sizeof(val));
success = 0;
sur = bsearch(a);
des = bsearch(b);
if(sur != -1 && des != -1) {
if(sur == des)
success = 1;
q.push(sur);
val[sur] = sur;
while(!q.empty() && !success) { //BFS
i = q.front();
q.pop();
for(t = adj[i]; t != z; t = t->next) {
if(val[t->v] == -1) {
q.push(t->v);
val[t->v] = i;
if(t->v == des) {
success = 1;
break;
}
}
}
}
}
if(success) { //print the path
i = 1;
path[0] = des;
for(int dad = val[des]; dad != sur ; i++, dad = val[dad]) {
path[i] = dad;
}
path[i] = sur;
for( ; i >= 0; i--)
cout<<dic[path[i]]<<endl;
}
else cout<<"No solution."<<endl;
cout<<endl;
}
return 0;
}
Code: Select all
#include <iostream>
#include <set>
#include <string>
using namespace std;
set <string> dict;
string red,start,end;
void solve(string start, string end) {
string popis[500],sol[20];
int pi[500],dno=0,vrh=1;
popis[0]=start;
pi[0]=0;
bool gotovo=false;
while (dno<vrh && !gotovo) {
string r=popis[dno];
for (int i=0; i<r.size(); i++)
if (r[i]!=end[i]) {
string r2=r;
r2[i]=end[i];
if (dict.find(r2)!=dict.end()) {
popis[vrh]=r2;
pi[vrh]=dno;
if (r2==end) {
gotovo=true;
break;
}
vrh++;
}
}
dno++;
}
if (!gotovo) {
cout << "No solution." << endl << endl;;
return;
}
int natrag=vrh,br=0;
while (natrag) {
sol[br++]=popis[natrag];
natrag=pi[natrag];
}
cout << start << endl;
for (int i=br-1; i>=0; i--)
cout << sol[i] << endl;
cout << endl;
}
int main() {
getline(cin,red);
while (red!="") {
dict.insert(red);
getline(cin,red);
}
while (cin >> start >> end) {
if (start.size()!=end.size() || dict.find(start)==dict.end()
|| dict.find(end)==dict.end()) cout << "No solution." << endl << endl; else
if (start==end) cout << start << endl << endl; else
solve(start,end);
}
return 0;
}
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
vector<string> words;
int dist[25143];
int parent[25143];
int binary_search(string s)
{
int low = -1, high = words.size(), mid;
while (high - low > 1)
{
mid = (high + low) / 2;
if (words[mid] > s)
high = mid;
else
low = mid;
}
if (low == -1 || words[low] != s)
return -1;
else
return low;
}
void bfs(int start, int end)
{
queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty())
{
int thisPos = q.front();
if (thisPos == end)
break;
q.pop();
for (int i = 0; i < words[thisPos].size(); ++i)
{
// Work on changing character i
string w = words[thisPos];
for (int c = 'a'; c <= 'z'; ++c)
{
if (c == words[thisPos][i])
continue;
w[i] = c;
int m = binary_search(w);
if (m != -1 && dist[m] == -1)
{
// Haven't seen it yet so enqueue
dist[m] = dist[thisPos] + 1;
parent[m] = thisPos;
q.push(m);
}
}
}
}
if (q.empty())
cout << "No solution." << endl;
else
{
// Reverse the output order
stack<string> s;
int pos = end;
while (parent[pos] != -1)
{
s.push(words[pos]);
pos = parent[pos];
}
cout << start << endl;
while (!s.empty())
{
cout << s.top() << endl;
s.pop();
}
}
}
int main()
{
string s;
while (getline(cin, s))
{
if (s.size() == 0)
break;
words.push_back(s);
}
sort(words.begin(), words.end());
string s1, s2;
while (getline(cin, s))
{
if (s.size() == 0)
break;
istringstream istr(s);
istr >> s1 >> s2;
// Initialize arrays
for (int i = 0; i < words.size(); ++i)
parent[i] = dist[i] = -1;
int n1 = binary_search(s1), n2 = binary_search(s2);
if (n1 == -1 || n2 == -1)
cout << "No solution." << endl;
else
bfs(n1, n2);
cout << endl;
}
}
Code: Select all
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
// At most 25,143 words
#define INF 30000
#define DEBUG false
using namespace std;
typedef unsigned short Int;
// Binary Search (Iterative version, to avoid stack overflow)
Int binSrch(vector<string>& dict, string val, Int left, Int right) {
if(DEBUG) cout<<"Bsearch: "<<val<<'\n';
Int mid;
while (left <= right) {
mid = (left+right)/2;
if(DEBUG)cout<<"left: "<<left<<"\tmid: "<<mid<<"\tright: "<<right<<'\n';
if(dict[mid]==val) return mid;
if(val<dict[mid]) {
if (mid==0) break;
right=mid-1;
}
else if(val>dict[mid]) left=mid+1;
}
return INF;
}
void BFS(vector<string>& dict,
vector<Int>& p,
Int size,
Int& s, Int& d, bool& noSoln) {
queue<Int> Q;
string tmp;
string uStr;
Int u,v;
vector<char> visited(size, 'w');
for(Int i=0;i<size;i++) p[i]=INF;
visited[s]='g';
Q.push(s);
while(!Q.empty()) {
u=Q.front();
uStr=dict[u];
if(DEBUG) cout<<"dict[u]: "<<dict[u]<<'\n';
for(Int i=0;i<uStr.size();i++) {
for(char j='a';j<='z';j++) {
tmp=uStr;
if(tmp[i]!=j) {
tmp[i]=j;
v=binSrch(dict,tmp,0,size-1);
if (v!=INF && visited[v]=='w') {
visited[v]='g';
p[v] = u;
if (v==d) {
noSoln=false;
return;
}
Q.push(v);
}
}
}
}
if (DEBUG)cout<<"Q size: "<<Q.size()<<'\n';
Q.pop();
visited[u]='b';
} // while
noSoln=true;
}
// remove duplicate strings in the vector parameter
void getUnique(vector<string>& v) {
string cur="";
for(vector<string>::iterator i=v.begin();i!=v.end();) {
if (cur!=*i) {
cur = *i;
++i;
}
else i=v.erase(i);
}
}
int main()
{
string line,fir,sec;
vector<string> dict;
vector<Int> p;
short testcases, numDiff;
bool noSoln;
stack<Int> output;
string * db;
Int size, firId, secId, prev;
istringstream instream;
while(getline(cin,line)&&line!="") dict.push_back(line);
sort(dict.begin(), dict.end());
getUnique(dict);
size = dict.size();
if(DEBUG)for(Int i=0;i<size;i++)cout<<dict[i]<<'\n';
testcases=1;
while(getline(cin,line)&&line!="") {
instream.clear();
instream.str(line);
instream >> fir >> sec;
if (DEBUG) cout<<"First: "<<fir<<" Second: "<<sec<<'\n';
firId = INF;
secId = INF;
for(Int i=0;i<size;i++) {
if (dict[i]==fir) firId = i;
if (dict[i]==sec) secId = i;
if (firId != INF && secId != INF) break;
}
if (DEBUG) cout<<"ID: "<<firId<<" "<<secId<<'\n';
noSoln = false;
if (firId == INF || secId == INF) noSoln=true;
else {
while (!output.empty()) output.pop();
if (p.empty()) p.resize(size);
BFS(dict, p, size, firId, secId, noSoln);
if(!noSoln) {
while (secId != firId) {
if(p[secId]==INF) {
noSoln=true;
break;
}
output.push(secId);
secId=p[secId];
}
output.push(firId);
}
}
// output
// print an extra line between test cases
if(testcases>=2) cout<<'\n';
testcases++;
// print the sequence
if (noSoln) cout<<"No solution."<<'\n';
else {
if(DEBUG) cout<<"Yes solution"<<'\n';
while(!output.empty()) {
cout<<dict[output.top()]<<'\n';
output.pop();
}
}
}
return 0;
}
Code: Select all
ab
xb
xy
dy
de
ab de
Code: Select all
// montagem do grafo
void montarGrafo ( void ){
register int i, j;
for ( i = 0; i < N - 1; i++ ){
for ( j = i + 1; j < N; j++ ){
if ( doublet ( word[i], word[j] ) ){
W[i].vizinho.push_back(j);
W[j].vizinho.push_back(i);
}
}
}
}
Code: Select all
Removed After AC
Code: Select all
AC 0.060