Find a Word

input/code.cpp: In function 'll has_duplicate(std::__cxx11::string&, ll, ll)':
input/code.cpp:38:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
                                     ~~~~~~~~~~~~^~~~
input/code.cpp:38:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
                                                           ~~~~~~~~~~~~^~~~

#include <bits/stdc++.h>

using namespace std;

typedef long long unsigned int ll;

char C[33][33];

#define GETX second.second.first
#define GETY second.first
#define GETCT second.second.second

set< pair< string, pair<int, pair<int,ll> > > > prevQ;
set< pair< string, pair<int, pair<int,ll> > > > nextQ;

ll n, k;

ll fact(ll x) {
    ll f = 1;
    for (ll i = 2; i <= x; ++i)
        f *= i;
    return f;
}

ll count_from(ll x, ll y) {
    ll nf = fact(n*2-2-x-y);
    ll df1 = fact(n-1-x);
    ll df2 = fact((n*2-2-x-y)-(n-1-x));
    
    return nf / (df1 * df2);
}

ll has_duplicate(string & s, ll x, ll y) {
    auto next_it = nextQ.upper_bound({s, {y ,{x, 0}}});
    
    if (next_it != nextQ.end()) {
        auto next_e = *next_it;
        if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
            nextQ.erase(next_it);
            return next_e.GETCT;
        }
        return 0;
    }
    return 0;
}

int main () {
    cin >> n >> k;
    
    for (ll i = 0; i < n; ++i) {
        string line;
        cin >> line;
        
        for (ll j = 0; j < n; ++j) {
            C[i][j] = line[j];
        }
    }
    
    string e = "";
    e += C[0][0];
    prevQ.insert({e, {0 , {0, 1}}});
 
    while (true) {
        if (prevQ.begin()->first.size() == 2*n-1) break;
    
        string prev_prefix = "";
        ll cumulative = 0;
        
        vector < pair< string, pair<int, pair<int,ll> > > > eraselist;
        
        for (auto elem : prevQ) {
            string s = elem.first;
            ll y = elem.GETY;
            ll x = elem.GETX;
            ll ct = elem.GETCT;
            
            ll m = ct * count_from(x,y);
            
            
            
            //cout << s << " " << m << " " << cumulative << endl;
            
            if (prev_prefix.size() && s > prev_prefix && cumulative >= k) {
                //cout << "remove me" << endl;
                eraselist.push_back(elem);
            }
            
            prev_prefix = s;
            
            cumulative += m;
        }
        
        for (auto elem : eraselist)
            prevQ.erase(elem);
        
        
        while (prevQ.size()) {
            
            auto elem = *prevQ.begin();
            prevQ.erase(prevQ.begin());
            
            string s = elem.first;
            ll y = elem.GETY;
            ll x = elem.GETX;
            ll ct = elem.GETCT;
            
            
            //cout << s << " " << ct << endl;
            
            if (x < n-1) {
                ll newx = x+1;
                ll newy = y;
                
                //ll newct = count_from(newx, newy);
                string new_s = s + C[newy][newx];
                ll lol = has_duplicate(new_s, newx, newy);
                nextQ.insert({new_s, {newy, {newx, ct+lol}}});
            }
            
            if (y < n-1) {
                ll newx = x;
                ll newy = y+1;
                
                //ll newct = count_from(newx, newy);
                string new_s = s + C[newy][newx];
                ll lol = has_duplicate(new_s, newx, newy);
                nextQ.insert({new_s, {newy, {newx, ct+lol}}});
            }
        }
        
        swap(nextQ, prevQ);
    }
    
    /*
    for (auto elem : prevQ) {
        cout << elem.first << " " << elem.GETCT << endl;
    }
    */
    
    cout << prevQ.rbegin()->first << endl;
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED