Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 13:51:38
Task:Find a Word
Sender:Wave of Technology
Submission time:2018-05-26 13:51:38
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.02 / 1.00details
#2ACCEPTED0.01 / 1.00details
#3ACCEPTED0.01 / 1.00details
#4ACCEPTED0.01 / 1.00details
#5ACCEPTED0.01 / 1.00details
#6ACCEPTED0.01 / 1.00details
#7ACCEPTED0.01 / 1.00details
#8ACCEPTED0.01 / 1.00details
#9ACCEPTED0.01 / 1.00details
#10ACCEPTED0.01 / 1.00details
#11ACCEPTED0.02 / 1.00details
#12ACCEPTED0.01 / 1.00details
#13ACCEPTED0.01 / 1.00details
#14ACCEPTED0.01 / 1.00details
#15ACCEPTED0.01 / 1.00details
#16ACCEPTED0.01 / 1.00details

Compiler report

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) {
       ^~

Code

#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 details

Test 1

Verdict: ACCEPTED

input
4 1
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 2

Verdict: ACCEPTED

input
4 2
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 3

Verdict: ACCEPTED

input
4 10
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 4

Verdict: ACCEPTED

input
4 19
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 5

Verdict: ACCEPTED

input
4 20
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 6

Verdict: ACCEPTED

input
4 1
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEVHXCV
view   save

user output
QEVHXCV
view   save

Test 7

Verdict: ACCEPTED

input
4 2
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEVHZCV
view   save

user output
QEVHZCV
view   save

Test 8

Verdict: ACCEPTED

input
4 10
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEXRXCV
view   save

user output
QEXRXCV
view   save

Test 9

Verdict: ACCEPTED

input
4 19
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QNVJZCV
view   save

user output
QNVJZCV
view   save

Test 10

Verdict: ACCEPTED

input
4 20
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QNVJZFV
view   save

user output
QNVJZFV
view   save

Test 11

Verdict: ACCEPTED

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 12

Verdict: ACCEPTED

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 13

Verdict: ACCEPTED

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...
view   save

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...
view   save

Test 15

Verdict: ACCEPTED

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save

user output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save

Test 16

Verdict: ACCEPTED

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save