# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
13242 | baneling100 | K-th path (IZhO11_kthpath) | C++98 | 26 ms | 16748 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define N_MAX 30
#define M_MAX 30
#define Data_MAX 1000000
int N, M, Data[Data_MAX+1][2], Cnt, Temp[Data_MAX+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();
break;
}
else
K-=sum;
j=k-1;
}
}
int main(void) {
input();
makeNum();
output();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |