1496:Word Index
keyword
概要
str[i] < str[i+1]となるような文字列を順に生成する(5桁。総数はたかだか90000個くらい)。文字列が与えられたときそれが何番目のものか求める問題。生成は問題無いのでTLEになる要素は無いのになぜか10回位TLEをもらう。G++ではなくC++で提出したら何故か無事AC。何だったんだろう…。
int main(){ char c = 'a' - 1, x[6], y[6], z[6]; int i, j, n=83681, m, low,mid,high; x[0]=x[1]=x[2]=x[3]=c; x[4]='a'; x[5]='\0'; z[5]='\0'; string str; string ws[83681]; REP(i,n-1){ ws[i]=string(x); if(x[4] < 'z'){ x[4]++; continue; } REP(j,5) if(x[4-j] != 'z' - j) break; x[4-j]++; for(j--;j>=0;j--) x[4-j] = x[(4-j)-1] + 1; } ws[i] = string(x); while(scanf("%s\n",y)!=EOF){ m = strlen(y); REP(i,5-m) z[i]=c; REP(i,m) z[i+5-m] = y[i]; str = string(z); if(!binary_search(ws, ws+n, str)) printf("0\n"); else{ low=0;high=n-1; while(1){ mid = (low+high)>>1; if(ws[mid] == str){ printf("%d\n",mid + 1); break; } if(ws[mid] < str){ low = mid + 1; } else high = mid - 1; } } } return 0; }