Submission #91687

#	Time	Username	Problem	Language	Result	Execution time	Memory
91687		SamAnd	K-th path (IZhO11_kthpath)	C++17	100 / 100	5 ms	848 KiB

kthpath

#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 (stderr)

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 / 100