oj.uz

Submission #13245

# Submission time Handle Problem Language Result Execution time Memory
13245 2015-02-05T14:32:39 Z baneling100 K-th path (IZhO11_kthpath) C++
100 / 100
 3 ms 1436 KB 
#include <stdio.h>
#define N_MAX 30
#define M_MAX 30
#define Data_MAX 10000

int N, M, Data[(Data_MAX<<1)+1][2], Cnt, Temp[(Data_MAX<<1)+1][2], TCnt, Count[27];
char Grid[N_MAX+1][M_MAX+2];
long long K, Num[N_MAX+1][M_MAX+1];

void input(void) {

    int i;

    scanf("%d %d",&N,&M);
    for(i=1 ; i<=N ; i++)
        scanf("%s",&Grid[i][1]);
    scanf("%lld",&K);
}

void makeNum(void) {

    int i, j;

    Num[0][1]=1;
    for(i=1 ; i<=N ; i++)
        for(j=1 ; j<=M ; j++)
            Num[i][j]=Num[i-1][j]+Num[i][j-1];
}

void countingSort(void) {

    int i;

    for(i=0 ; i<=26 ; i++)
        Count[i]=0;
    for(i=1 ; i<=Cnt ; i++)
        Count[Grid[Data[i][0]][Data[i][1]]-'a'+1]++;
    for(i=1 ; i<=26 ; i++)
        Count[i]+=Count[i-1];
    for(i=1 ; i<=Cnt ; i++) {
        Temp[++Count[Grid[Data[i][0]][Data[i][1]]-'a']][0]=Data[i][0];
        Temp[  Count[Grid[Data[i][0]][Data[i][1]]-'a']][1]=Data[i][1];
    }
    for(i=1 ; i<=Cnt ; i++) {
        Data[i][0]=Temp[i][0];
        Data[i][1]=Temp[i][1];
    }
}

void output(void) {

    int i, j, k;
    long long sum;

    Data[++Cnt][0]=1;
    Data[  Cnt][1]=1;
    for(i=1 ; i<=N+M-1 ; i++)
        for(j=1 ; j<=Cnt ; j++) {
            sum=0;
            for(k=j ; k<=Cnt ; k++) {
                if(k>j && Grid[Data[k][0]][Data[k][1]]!=Grid[Data[k-1][0]][Data[k-1][1]])
                    break;
                sum+=Num[N-Data[k][0]+1][M-Data[k][1]+1];
            }
            if(K<=sum) {
                printf("%c",Grid[Data[j][0]][Data[j][1]]);
                TCnt=0;
                for(k=j ; k<=Cnt ; k++) {
                    if(k>j && Grid[Data[k][0]][Data[k][1]]!=Grid[Data[k-1][0]][Data[k-1][1]])
                        break;
                    if(Data[k][0]+1<=N) {
                        Temp[++TCnt][0]=Data[k][0]+1;
                        Temp[  TCnt][1]=Data[k][1];
                    }
                    if(Data[k][1]+1<=M) {
                        Temp[++TCnt][0]=Data[k][0];
                        Temp[  TCnt][1]=Data[k][1]+1;
                    }
                }
                Cnt=TCnt;
                for(k=1 ; k<=TCnt ; k++) {
                    Data[k][0]=Temp[k][0];
                    Data[k][1]=Temp[k][1];
                }
                countingSort();
                if(Cnt>Data_MAX) {
                    Cnt=Data_MAX;
                    K=1;
                }
                break;
            }
            else
                K-=sum;
            j=k-1;
        }
}

int main(void) {

    input();
    makeNum();
    output();

    return 0;
}

Compilation message

kthpath.cpp: In function 'void input()':
kthpath.cpp:14:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
                         ^
kthpath.cpp:16:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&Grid[i][1]);
                                ^
kthpath.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&K);
                     ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1436 KB Output is correct
2 Correct 0 ms 1436 KB Output is correct
3 Correct 0 ms 1436 KB Output is correct
4 Correct 0 ms 1436 KB Output is correct
5 Correct 0 ms 1436 KB Output is correct
6 Correct 0 ms 1436 KB Output is correct
7 Correct 0 ms 1436 KB Output is correct
8 Correct 0 ms 1436 KB Output is correct
9 Correct 0 ms 1436 KB Output is correct
10 Correct 3 ms 1436 KB Output is correct
11 Correct 0 ms 1436 KB Output is correct
12 Correct 0 ms 1436 KB Output is correct
13 Correct 0 ms 1436 KB Output is correct
14 Correct 0 ms 1436 KB Output is correct
15 Correct 0 ms 1436 KB Output is correct
16 Correct 0 ms 1436 KB Output is correct
17 Correct 0 ms 1436 KB Output is correct
18 Correct 0 ms 1436 KB Output is correct
19 Correct 0 ms 1436 KB Output is correct
20 Correct 0 ms 1436 KB Output is correct