Find a Word

input/code.cpp: In function 'int main()':
input/code.cpp:48:6: warning: unused variable 'rem' [-Wunused-variable]
   ll rem = 1LL << (2*n-2);
      ^~~
input/code.cpp:51:6: warning: unused variable 'offset' [-Wunused-variable]
   ll offset = 0;
      ^~~~~~
input/code.cpp:107:7: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if (p.first == ch) {
       ^~

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> PLL;
 
const ll INF = 1000000000000000LL;
 
ll n;
 
ll choose(ll n, ll k) {
 
  k = min(k, n-k);
  
  ll res = 1;
  for (ll i=0; i<k; i++) {
    res *= (n-i);
    res /= (i+1);
  }
 
  return res;
  
}
 
ll countrem(PLL p) {
  ll i = p.first;
  ll j = p.second;
 
  return choose(2*n-2-i-j, n-1-i);
}
 
int main() {
 
  cin.tie(NULL);
  std::ios::sync_with_stdio(false);
 
  cin >> n;
 
  ll k;
  cin >> k;
 
  vector<string> s (n);
  for (int i=0; i<n; i++) {
    cin >> s[i];
  }
 
  ll rem = 1LL << (2*n-2);
 
 
  ll offset = 0;
 
  vector<vector<bool> > trythis(n, vector<bool>(n, false) );  
  trythis[0][0] = true;
  
  vector<vector<ll> > count(n, vector<ll>(n, 0) );  
  count[0][0] = 1;
  
  string res;
  res += s[0][0];
 
  
  for (int step=0; step<2*n-2; step++) {
 
    vector<pair<char, PLL> > poss;
 
    //    cout << "String: " << res << " k " << k << endl;
    
    
    for (int i=0; i<n; i++) {
      int j = step-i;
      if (j<0 || j>=n) { continue; }
 
      if (!trythis[i][j] ) { continue; }
 
      if (i<n-1) {
	poss.push_back(make_pair(s[i+1][j], make_pair(i+1, j)));
	count[i+1][j] += count[i][j];
      }
      if (j<n-1) {
	poss.push_back(make_pair(s[i][j+1], make_pair(i, j+1)));
	count[i][j+1] += count[i][j];
      }
      
    }
 
    sort(poss.begin(), poss.end());
 
    auto it = unique(poss.begin(), poss.end());
    poss.resize(it - poss.begin());
 
 
    ll thiscum = 0;
    char ch;
    for (auto p : poss) {
      //      cout << " Test pos: " << p.second.first << " " << p.second.second << " rem " << countrem(p.second) << " count to this " << count[p.second.first][p.second.second] << endl;
      thiscum += countrem(p.second) * count[p.second.first][p.second.second];
      if (thiscum >= k) {
	ch = p.first;
	//	cout << " Char: " << ch << endl;
	break;
      }
    }
    
    bool isprev = true;
    for (auto p : poss) {
      if (p.first == ch) {
	trythis[p.second.first][p.second.second] = true;
	isprev = false;
      } else if (isprev) {
	k -= countrem(p.second) * count[p.second.first][p.second.second];
     }
    }
 
    res += ch;
    
  }
 
  cout << res << endl;
 
  return 0;
}

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: ACCEPTED

Test 16

Verdict: ACCEPTED