123 Searching Quickly

[C8H10N4O2]

Does anyone know of any special cases? My code works for the example case but gives me WA.
[cpp]
#pragma warning (disable:4786)
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>
#include <cstring>

using namespace std;

void main()
{
char B[1000],*P;
int i,j,k,N;
bool Duplicate;
vector<string> Ignore;
vector<string> Titles;
map<string,vector<int> > Index;
map<string,vector<int> >::iterator Idx;
string Title,Word,UWord;

do
{
scanf("%s",B);
for(i=0;i<strlen(B);i++)
{
B[i]=tolower(B[i]);
}
Ignore.push_back(B);
}
while(strcmp(B,"::")!=0);
Ignore.pop_back();

scanf("\n");
N=0;
while(fgets(B,1000,stdin)!=NULL)
{
for(i=0;i<strlen(B);i++)
{
B[i]=tolower(B[i]);
}
P=strchr(B,'\n');
if(P)
*P='\0';
Titles.push_back(B);

Title="";
P=strtok(B," ");
Duplicate=false;
while(P)
{
if(find(Ignore.begin(),Ignore.end(),P)==Ignore.end())
{
if(Title=="")
{
Title+=P;
}
else
{
Title+=" ";
Title+=P;
}
if(find(Index[P].begin(),Index[P].end(),N)==Index[P].end())
{
Index[P].push_back(N);
}
}

P=strtok(NULL," ");
}
N++;
}

for(Idx=Index.begin();Idx!=Index.end();Idx++)
{
for(i=0;i<(*Idx).second.size();i++)
{
k=-1;
Word=(*Idx).first;
UWord=Word;
Title=Titles[(*Idx).second[i]];
for(j=0;j<Word.size();j++)
{
UWord[j]=toupper(UWord[j]);
}
while(true)
{
k=Title.find(Word,k+1);
if(k!=string::npos)
{
printf("%s",Title.substr(0,k).c_str());
printf("%s",UWord.c_str());
printf("%s\n",Title.substr(k+Word.size(),Title.size()-k-Word.size()).c_str());
}
else
{
break;
}
}
}
}
}[/cpp]

[bodq]

Does anyone know of any special cases? My code works for the example case but gives me WA.

I guess I'll spoil you the fun if I'd tell you what exactly is wrong, so here is just the test case:

foo
::
o a foozoobar

have a nice day!

[C8H10N4O2]

Thanks, I will look into it:)

[Rossi]

runtime error?????

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

typedef struct{
int len;
char *main;
}TITLE;

int compstr(const void *a,const void *b)
{return strcmp((char *)a,(char *)b);}

int compptr(const void *a,const void *b)
{return strcmp(*(char **)a,*(char **)b);}

void print(char *,char *);
void strlower(char *);
int searchkey(char *);
char *instr(char *,char *);

int knum;
char keys[52][16];

int main(void)
{
register int i,j;
int tnum,rnum;
char str[16384],*p;
char *arr[3200];
TITLE ttl[210];

for(knum=0;;knum++){
gets(str);
p=strtok(str," \t");
strcpy(keys[knum],p);
if(strcmp(keys[knum],"::")==0)
break;
strlower(keys[knum]);
}

qsort((void *)keys,knum,sizeof(keys[0]),compstr);

for(tnum=rnum=0;;tnum++){
if(gets(str)==NULL)
break;

ttl[tnum].len=strlen(str);
ttl[tnum].main=new char[ttl[tnum].len+1];
strlower(str);
strcpy(ttl[tnum].main,str);

p=strtok(str," \t");
for(;p;){
if(searchkey(p)==0){
arr[rnum]=new char[strlen(p)+1];
strcpy(arr[rnum],p);
rnum++;
}
p=strtok(NULL," \t");
}
}

qsort((void *)arr,rnum,sizeof(char *),compptr);

for(i=0;i<rnum;i++){
for(j=0;j<tnum;j++){
if((p=instr(ttl[j].main,arr[i]))!=NULL){
print(ttl[j].main,p);
break;
}
}
}

for(i=0;i<tnum;i++)
delete []ttl[i].main;

for(i=0;i<rnum;i++)
delete []arr[i];

return 0;
}

void strlower(char *str)
{
while(*str){
*str=tolower(*str);
str++;
}
}

int searchkey(char *key)
{
int res,left,right,mid;

left=0;
right=knum-1;
while(left<=right){
mid=(left+right)/2;
res=strcmp(key,keys[mid]);
if(res<0)
right=mid-1;
else if(res>0)
left=mid+1;
else
return 1;
}
return 0;
}

void print(char *in,char *p)
{
strlower(in);
while(!isspace(*p)){
*p=toupper(*p);
p++;
}
printf("%s\n",in);
}

char *instr(char *src,char *sub)
{
register int i,j;
int lsrc,lsub;

lsrc=strlen(src);
lsub=strlen(sub);

for(i=0;i<lsrc;i++){
if((i==0||isspace(src[i-1]))&&src[i]==sub[0]){
for(j=1;j<lsub;j++){
if(src[j+i]!=sub[j])
break;
}
if(j==lsub&&(src[j+i]==NULL||isspace(src[j+i]))){
return ((char *)&src[i]);
}
}
}

return NULL;
}[/cpp]

[C8H10N4O2]

The runtime error is probably due to the gratuitous use of pointers... Try running through it with a debugger. There is probably an indexOutOfBounds exception somewhere.

[sefakilic]

Hello, I am getting WA for the problem.
Here is my code, i can't find the error.

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
using namespace std;
string ignores[50];
string titles[200];
struct x {
    string potential;
    int index;
    int indexintitle;
};
vector<struct x> potentials;
vector<string> titlewords;

string toLower(string x)
{
    // assuming string x contains only [A-Z] and [a-z]
    int len = x.length();
    for(int i = 0; i < len; ++i)
    {
        if(x[i] >= 'A' && x[i] <= 'Z')
            x[i] = x[i] + 32;
    }
    return x;
}

string toUpper(string x)
{
    // assuming string x contains only [A-Z] and [a-z]
    int len = x.length();
    for(int i = 0; i < len; ++i)
    {
        if(x[i] >= 'a' && x[i] <= 'z')
            x[i] = x[i] - 32;
    }
    return x;
}


bool cmp (struct x a, struct x b)
{
    if(toLower(a.potential) != toLower(b.potential))
        return (toLower(a.potential) < toLower(b.potential));
    else return (a.index < b.index);
}
int main()
{
    string tmp;
    int numberignores = 0;
    int numbertitles = 0;
    stringstream ss;
   
    while(cin >> tmp)
    {
        if(tmp == "::") break;
        else ignores[numberignores++] = tmp;
    }
    sort(ignores, ignores + numberignores);
    while(getline(cin, tmp))
    {
        if(tmp.length() == 0) continue;
        titles[numbertitles++] = tmp;
    }
    potentials.clear();
    for(int i = 0; i < numbertitles; ++i)
    {
        //cout << "|" << titles[i] << "|" << endl;
        titlewords.clear();
        ss.clear();
        ss.str(titles[i]);
        while(ss >> tmp)
            titlewords.push_back(tmp);

        for(vector<string>::iterator it = titlewords.begin(); it != titlewords.end(); ++it)
        {
            //cout << "x: " << *it << " " << toLower(*it) << endl;
            if(binary_search(ignores, ignores + numberignores, toLower(*it)) == false)
            {
                //cout << "potential: " << *it << endl;
                struct x tmpx;
                tmpx.potential = *it;
                tmpx.index     = i;
                tmpx.indexintitle = it - titlewords.begin();
                potentials.push_back(tmpx);
            }
        }
       
    }
    sort(potentials.begin(), potentials.end(), cmp);
   
    for(vector<struct x>::iterator it = potentials.begin(); it != potentials.end(); ++it)
    {
        struct x tmpx = *it;
        ss.clear();
        ss.str(titles[tmpx.index]);
        bool first = true;
        int wordcount  = 0;
        while(ss >> tmp)
        {
            wordcount += 1;
            if(first) { first = false; }
            else cout << " ";
            if(tmp == tmpx.potential && tmpx.indexintitle + 1 == wordcount) cout << toUpper(tmp);
            else cout << toLower(tmp);
        }
        cout << endl;
    }
   
    return 0;
}
   


[Sedefcho]

Here is a wikipedia article which was changed a little
bit in order to match this problem's requirements.

INPUT

Code: Select all

the
for
on
in
and
is
it
american
canadian
great
lakes
::
The Niagara Falls are voluminous waterfalls on the Niagara River
straddling the international border between the Canadian province
of Ontario and the U S  state of New York  The falls are
N miles BBBBBBSSSM kmBBBBBBSSS north northwest of Buffalo New York and
S miles BBBBBBSSSZ kmBBBBBBSSS south southeast of Toronto Ontario
between the twin cities of Niagara Falls Ontario
and Niagara Falls New York  Niagara Falls is composed
of two major sections separated by Goat Island:
Horseshoe Falls the majority of which lies on the
Canadian side of the border and American Falls on the
American side  The smaller Bridal Veil Falls are also
located on the American side separated from the main falls
by Luna Island  Niagara Falls were formed when glaciers
receded at the end of the Wisconsin glaciation BBBBBBSSSthe last ice ageBBBBBBSSS
and water from the newly formed Great Lakes carved a path through
the Niagara Escarpment en route to the Atlantic Ocean
While not exceptionally high the Niagara Falls are very wide
More than six million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS of water falls
over the crest line every minute in high flow and almost
F million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS on average  It is the most
powerful waterfall in North America

The Niagara Falls are renowned both for their beauty and
as a valuable source of hydroelectric power  Managing the
balance between recreational commercial and industrial uses
has been a challenge for the stewards of the falls since the TKLMs


OUTPUT

Code: Select all

and water from the newly formed great lakes carved A path through
as A valuable source of hydroelectric power  managing the
has been A challenge for the stewards of the falls since the tklms
receded at the end of the wisconsin glaciation bbbbbbsssthe last ice AGEBBBBBBSSS
over the crest line every minute in high flow and ALMOST
american side  the smaller bridal veil falls are ALSO
powerful waterfall in north AMERICA
the niagara falls ARE voluminous waterfalls on the niagara river
of ontario and the u s  state of new york  the falls ARE
american side  the smaller bridal veil falls ARE also
while not exceptionally high the niagara falls ARE very wide
the niagara falls ARE renowned both for their beauty and
AS a valuable source of hydroelectric power  managing the
receded AT the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara escarpment en route to the ATLANTIC ocean
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on AVERAGE  it is the most
BALANCE between recreational commercial and industrial uses
n miles BBBBBBSSSM kmbbbbbbsss north northwest of buffalo new york and
receded at the end of the wisconsin glaciation BBBBBBSSSTHE last ice agebbbbbbsss
more than six million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss of water falls
f million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss on average  it is the most
s miles BBBBBBSSSZ kmbbbbbbsss south southeast of toronto ontario
the niagara falls are renowned both for their BEAUTY and
has BEEN a challenge for the stewards of the falls since the tklms
straddling the international border BETWEEN the canadian province
BETWEEN the twin cities of niagara falls ontario
balance BETWEEN recreational commercial and industrial uses
straddling the international BORDER between the canadian province
canadian side of the BORDER and american falls on the
the niagara falls are renowned BOTH for their beauty and
american side  the smaller BRIDAL veil falls are also
n miles bbbbbbsssm kmbbbbbbsss north northwest of BUFFALO new york and
of two major sections separated BY goat island:
BY luna island  niagara falls were formed when glaciers
and water from the newly formed great lakes CARVED a path through
has been a CHALLENGE for the stewards of the falls since the tklms
between the twin CITIES of niagara falls ontario
balance between recreational COMMERCIAL and industrial uses
and niagara falls new york  niagara falls is COMPOSED
over the CREST line every minute in high flow and almost
more than six million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
the niagara escarpment EN route to the atlantic ocean
receded at the END of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara ESCARPMENT en route to the atlantic ocean
over the crest line EVERY minute in high flow and almost
while not EXCEPTIONALLY high the niagara falls are very wide
F million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
the niagara FALLS are voluminous waterfalls on the niagara river
of ontario and the u s  state of new york  the FALLS are
between the twin cities of niagara FALLS ontario
and niagara FALLS new york  niagara falls is composed
and niagara falls new york  niagara FALLS is composed
horseshoe FALLS the majority of which lies on the
canadian side of the border and american FALLS on the
american side  the smaller bridal veil FALLS are also
located on the american side separated from the main FALLS
by luna island  niagara FALLS were formed when glaciers
while not exceptionally high the niagara FALLS are very wide
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water FALLS
the niagara FALLS are renowned both for their beauty and
has been a challenge for the stewards of the FALLS since the tklms
more than six million cubic FEET bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic FEET bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
over the crest line every minute in high FLOW and almost
by luna island  niagara falls were FORMED when glaciers
and water from the newly FORMED great lakes carved a path through
located on the american side separated FROM the main falls
and water FROM the newly formed great lakes carved a path through
receded at the end of the wisconsin GLACIATION bbbbbbsssthe last ice agebbbbbbsss
by luna island  niagara falls were formed when GLACIERS
of two major sections separated by GOAT island:
HAS been a challenge for the stewards of the falls since the tklms
while not exceptionally HIGH the niagara falls are very wide
over the crest line every minute in HIGH flow and almost
HORSESHOE falls the majority of which lies on the
as a valuable source of HYDROELECTRIC power  managing the
receded at the end of the wisconsin glaciation bbbbbbsssthe last ICE agebbbbbbsss
balance between recreational commercial and INDUSTRIAL uses
straddling the INTERNATIONAL border between the canadian province
by luna ISLAND  niagara falls were formed when glaciers
of two major sections separated by goat ISLAND:
n miles bbbbbbsssm KMBBBBBBSSS north northwest of buffalo new york and
s miles bbbbbbsssz KMBBBBBBSSS south southeast of toronto ontario
receded at the end of the wisconsin glaciation bbbbbbsssthe LAST ice agebbbbbbsss
horseshoe falls the majority of which LIES on the
over the crest LINE every minute in high flow and almost
LOCATED on the american side separated from the main falls
by LUNA island  niagara falls were formed when glaciers
located on the american side separated from the MAIN falls
of two MAJOR sections separated by goat island:
horseshoe falls the MAJORITY of which lies on the
as a valuable source of hydroelectric power  MANAGING the
n MILES bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
s MILES bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
more than six MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
over the crest line every MINUTE in high flow and almost
MORE than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the MOST
more than six million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS of water falls
f million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS on average  it is the most
N miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
of ontario and the u s  state of NEW york  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo NEW york and
and niagara falls NEW york  niagara falls is composed
and water from the NEWLY formed great lakes carved a path through
the NIAGARA falls are voluminous waterfalls on the niagara river
the niagara falls are voluminous waterfalls on the NIAGARA river
between the twin cities of NIAGARA falls ontario
and NIAGARA falls new york  niagara falls is composed
and niagara falls new york  NIAGARA falls is composed
by luna island  NIAGARA falls were formed when glaciers
the NIAGARA escarpment en route to the atlantic ocean
while not exceptionally high the NIAGARA falls are very wide
the NIAGARA falls are renowned both for their beauty and
n miles bbbbbbsssm kmbbbbbbsss NORTH northwest of buffalo new york and
powerful waterfall in NORTH america
n miles bbbbbbsssm kmbbbbbbsss north NORTHWEST of buffalo new york and
while NOT exceptionally high the niagara falls are very wide
the niagara escarpment en route to the atlantic OCEAN
OF ontario and the u s  state of new york  the falls are
of ontario and the u s  state OF new york  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest OF buffalo new york and
s miles bbbbbbsssz kmbbbbbbsss south southeast OF toronto ontario
between the twin cities OF niagara falls ontario
OF two major sections separated by goat island:
horseshoe falls the majority OF which lies on the
canadian side OF the border and american falls on the
receded at the end OF the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss OF water falls
as a valuable source OF hydroelectric power  managing the
has been a challenge for the stewards OF the falls since the tklms
of ONTARIO and the u s  state of new york  the falls are
s miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ONTARIO
between the twin cities of niagara falls ONTARIO
OVER the crest line every minute in high flow and almost
and water from the newly formed great lakes carved a PATH through
as a valuable source of hydroelectric POWER  managing the
POWERFUL waterfall in north america
straddling the international border between the canadian PROVINCE
RECEDED at the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
balance between RECREATIONAL commercial and industrial uses
the niagara falls are RENOWNED both for their beauty and
the niagara falls are voluminous waterfalls on the niagara RIVER
the niagara escarpment en ROUTE to the atlantic ocean
of ontario and the u S  state of new york  the falls are
S miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
of two major SECTIONS separated by goat island:
of two major sections SEPARATED by goat island:
located on the american side SEPARATED from the main falls
canadian SIDE of the border and american falls on the
american SIDE  the smaller bridal veil falls are also
located on the american SIDE separated from the main falls
has been a challenge for the stewards of the falls SINCE the tklms
more than SIX million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
american side  the SMALLER bridal veil falls are also
as a valuable SOURCE of hydroelectric power  managing the
s miles bbbbbbsssz kmbbbbbbsss SOUTH southeast of toronto ontario
s miles bbbbbbsssz kmbbbbbbsss south SOUTHEAST of toronto ontario
of ontario and the u s  STATE of new york  the falls are
has been a challenge for the STEWARDS of the falls since the tklms
STRADDLING the international border between the canadian province
more THAN six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
the niagara falls are renowned both for THEIR beauty and
and water from the newly formed great lakes carved a path THROUGH
has been a challenge for the stewards of the falls since the TKLMS
the niagara escarpment en route TO the atlantic ocean
s miles bbbbbbsssz kmbbbbbbsss south southeast of TORONTO ontario
between the TWIN cities of niagara falls ontario
of TWO major sections separated by goat island:
of ontario and the U s  state of new york  the falls are
balance between recreational commercial and industrial USES
as a VALUABLE source of hydroelectric power  managing the
american side  the smaller bridal VEIL falls are also
while not exceptionally high the niagara falls are VERY wide
the niagara falls are VOLUMINOUS waterfalls on the niagara river
and WATER from the newly formed great lakes carved a path through
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of WATER falls
powerful WATERFALL in north america
the niagara falls are voluminous WATERFALLS on the niagara river
by luna island  niagara falls WERE formed when glaciers
by luna island  niagara falls were formed WHEN glaciers
horseshoe falls the majority of WHICH lies on the
WHILE not exceptionally high the niagara falls are very wide
while not exceptionally high the niagara falls are very WIDE
receded at the end of the WISCONSIN glaciation bbbbbbsssthe last ice agebbbbbbsss
of ontario and the u s  state of new YORK  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new YORK and
and niagara falls new YORK  niagara falls is composed


[at5anpo3]

The example above should be missing ":" from

Code: Select all

by Goat Island:

The output file MUST end with a \n, or else you fail the judge! (had to find it the hard way).

Best Regards,
at5anpo3