1496:Word Index

keyword

C++

概要

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;
}