oj.uz

Submission #91687

# Submission time Handle Problem Language Result Execution time Memory
91687 2018-12-29T07:47:13 Z SamAnd K-th path (IZhO11_kthpath) C++17
100 / 100
 5 ms 848 KB 
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=33,M=26;
struct ban
{
    int x,y;
};
struct ban1
{
    long long l,r;
};

int an;
char as[N+N];
int n,m;
char a[N][N];
long long k;
long long b[M][N][N],bb[M][N][N];
ban1 d[M];
long long z[N+N][N+N];
void pkk()
{
    z[0][0]=1;
    for(int i=1;i<N+N;++i)
    {
        z[i][0]=1;
        for(int j=1;j<=i;++j)
            z[i][j]=z[i-1][j]+z[i-1][j-1];
    }
}
long long tq(int x,int y)
{
    int mm=m-y-1;
    int nn=n-x-1+mm;
    return z[nn][mm];
}
void cl()
{
    for(int i=0;i<M;++i)
    {
        for(int ii=0;ii<n;++ii)
			for(int jj=0;jj<m;++jj)
				bb[i][ii][jj]=0;
        d[i].l=0;
        d[i].r=0;
    }
}
int main()
{
    //freopen("H.in","r",stdin);
    //freopen("H.out","w",stdout);
    int i,j,ii,jj;
    cin>>n>>m;
    for(i=0;i<n;++i)
        cin>>a[i];
    cin>>k;
    pkk();
    //////////////////////////
    ban t;
    d[a[0][0]-'a'].l=1;
    d[a[0][0]-'a'].r=tq(0,0);
    b[a[0][0]-'a'][0][0]=1;
    while(an<(n+m-1))
    {
        if(an==3)
            cout<<"";
        for(int i=0;i<M;++i)
        {
            long long l=d[i].l;
            long long r=d[i].r;
            if(k>=l && k<=r)
            {
                as[an]=(i+'a');
                ++an;
                cl();
                for(int ii=0;ii<n;++ii)
                {
					for(int jj=0;jj<m;++jj)
					{
                        ban h;
                        t.x=ii;
						t.y=jj;
                        h=t;
                        h.x++;
                        if(h.x<n && h.y<m)
                        {
							d[a[h.x][h.y]-'a'].r+=(b[i][t.x][t.y]*tq(h.x,h.y));
							bb[a[h.x][h.y]-'a'][h.x][h.y]+=b[i][t.x][t.y];
                        }

                        h=t;
                        h.y++;
                        if(h.x<n && h.y<m)
                        {
							d[a[h.x][h.y]-'a'].r+=(b[i][t.x][t.y]*tq(h.x,h.y));
							bb[a[h.x][h.y]-'a'][h.x][h.y]+=b[i][t.x][t.y];
                        }
					}
                }
                for(int j=0;j<M;++j)
                {
                    d[j].l=l;
                    d[j].r+=l;
                    d[j].r--;
                    l=d[j].r+1;
					for(int ii=0;ii<n;++ii)
						for(int jj=0;jj<m;++jj)
							b[j][ii][jj]=bb[j][ii][jj];
                }
                break;
            }
        }
    }
    for(int i=0;i<an;++i)
        cout<<as[i];
    cout<<endl;
    return 0;
}
/*
3 4
abcd
efdg
hijk
4
*/

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:56:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,ii,jj;
           ^
kthpath.cpp:56:13: warning: unused variable 'ii' [-Wunused-variable]
     int i,j,ii,jj;
             ^~
kthpath.cpp:56:16: warning: unused variable 'jj' [-Wunused-variable]
     int i,j,ii,jj;
                ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 764 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 4 ms 760 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 5 ms 760 KB Output is correct
16 Correct 4 ms 760 KB Output is correct
17 Correct 4 ms 760 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 4 ms 824 KB Output is correct
20 Correct 4 ms 764 KB Output is correct