Submission #883685

#	Time	Username	Problem	Language	Result	Execution time	Memory
883685		heeheeheehaaw	K-th path (IZhO11_kthpath)	C++17	0 / 100	0 ms	348 KiB

kthpath

#include <bits/stdc++.h>
#define int long long

using namespace std;

int comb[62][62];
int a[32][32];
bool visited[32][32];
string from[32][32];
int dx[] = {0, 1};
int dy[] = {1, 0};
int apare[32];
int cnt[32][32];
const int llm = 1000000000000000001;

int calc(int x, int y, int n, int m)
{
    return comb[n - x + m - y][m - y];
}

signed main()
{
    int n, m, k;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char c;
            cin>>c;
            a[i][j] = (int)c - 'a' + 1;
        }
    cin>>k;
    for(int i = 0; i <= 60; i++)
        comb[i][0] = 1, comb[i][i] = 1;
    for(int i = 1; i <= 60; i++)
        for(int j = 1; j < i; j++)
        {
            if(comb[i - 1][j] + comb[i - 1][j - 1] >= llm)
                comb[i][j] == llm;
            else
                comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }

    vector<pair<int, int>> v;
    int curr = 0;
    v.push_back({1, 1});
    from[1][1] = "a";
    cnt[1][1] = 1;
    while(!v.empty())
    {
        vector<pair<int, int>> aux;
        for(int i = 1; i <= 26; i++)
            apare[i] = 0;
        for(auto it : v)
        {
            int x = it.first, y = it.second;
            for(int dir = 0; dir < 2; dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                int cv = calc(nx, ny, n, m);
                if(cv <= llm / cnt[x][y])
                    cv *= cnt[x][y];
                else
                    cv = llm;
                apare[a[nx][ny]] += cv;
                cnt[nx][ny] += cnt[x][y];
                if(apare[a[nx][ny]] >= llm)
                    apare[a[nx][ny]] = llm;
                aux.push_back({nx, ny});
            }
        }

        aux.clear();
        int ch;
        for(int i = 1; i <= 26; i++)
        {
            if(apare[i] != 0)
            {
                int newc = curr + apare[i];
                if(k > curr && k <= newc)
                {
                    ch = i;
                    break;
                }
                else
                {
                    curr = newc;
                }
            }
        }

        for(auto it : v)
        {
            int x = it.first, y = it.second;
            for(int dir = 0; dir < 2; dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if(nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny] || a[nx][ny] != ch)
                    continue;
                visited[nx][ny] = true;
                aux.push_back({nx, ny});
                from[nx][ny] = from[x][y];
                from[nx][ny].push_back((char)ch + 'a' - 1);
            }
        }

        v = aux;
    }

    cout<<from[n][m];
    return 0;
}

/**

3 4
abcd
efdg
hijk
4

*/

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:39:28: warning: statement has no effect [-Wunused-value]
   39 |                 comb[i][j] == llm;
      |                 ~~~~~~~~~~~^~~~~~
kthpath.cpp:107:55: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |                 from[nx][ny].push_back((char)ch + 'a' - 1);
      |                                        ~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 100