CSES - HIIT Open 2018 - Results
Submission details
Task:Find a Word
Sender:Tefyn virallinen maajoukkue
Submission time:2018-05-26 15:17:30 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.02 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails

Code

#include <bits/stdc++.h>

using namespace std;
int n;
string s[33];
int64_t r[33][33];
string pp[33][33];
int np[33][33];
string hae(string lol, int64_t k, int64_t a, int64_t b, int i, int j){
    //cout << lol+s[i][j] << " " << k << " " << a << " " << b << " " << i << " " << j << " " << np[i][j] << " " <<pp[i][j] << endl;
    if(k < a || k >= b){
       // cout << "re1" << endl;
        return "";
    }
    if(i == n-1 && j == n-1){
        if(k >= a && k < b)
            return lol+s[i][j];
        return "";
    }
        
    if(i < n-1 && j < n-1){
        if(s[i+1][j] < s[i][j+1]){
            int64_t down = r[i+1][j];
            string re = hae(lol+s[i][j], k, a, a+down, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a+down, b, i, j+1);
            }
            return re;
        }
        else if(s[i+1][j] > s[i][j+1]){
            int64_t ri = r[i][j+1];
            string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
            }
            return re;
        }
        else {
            int64_t ri = r[i][j+1];
            int64_t down = r[i+1][j];
            if(np[i][j] == 1){
                string re3 = hae(lol+s[i][j], k, a, a+down, i+1, j);
                if(re3.length() == 0){
                    re3 = hae(lol+s[i][j], k, a+down, b, i, j+1);
                }
                return re3;
            }
            else {
                string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
                if(re.length() == 0){
                    re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
                }
                return re;
            }
        }
    }
    else if(i < n-1){
        return hae(lol+s[i][j], k, a, b, i+1, j);
    }
    else if(j < n-1){
        return hae(lol+s[i][j], k, a, b, i, j+1);
    }
    return "";
}


int main(){
    int64_t k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
    r[n-1][n-1] = 1;
    pp[n-1][n-1] = s[n-1][n-1];
    for(int i = n-1; i >= 0; --i){
        for(int j = n-1; j >= 0; --j){
            string c1 = "0";
            c1[0] = 'Z'+1;
            string c2 = "0";
            c2[0] = 'Z'+1;
            if(i < n-1){
                r[i][j] += r[i+1][j];
                c1 = s[i][j]+pp[i+1][j];
            }
            if(j< n-1){
                r[i][j] += r[i][j+1];
                c2 = s[i][j]+pp[i][j+1];
            }
            if(i < n-1 || j < n-1){
                if(c1 < c2){
                    np[i][j] = 1;
                    pp[i][j] = c1;
                }
                else{
                    pp[i][j] = c2;
                }
            }
            //cout << i << " " << j << " " << pp[i][j] << endl;
        }
    }
    cout << hae("", k-1, 0, r[0][0], 0, 0) << endl;
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
4 1
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 2

Verdict: ACCEPTED

input
4 2
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 3

Verdict: ACCEPTED

input
4 10
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 4

Verdict: ACCEPTED

input
4 19
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 5

Verdict: ACCEPTED

input
4 20
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 6

Verdict: ACCEPTED

input
4 1
QNJP
EVJU
XHZF
RXCV

correct output
QEVHXCV

user output
QEVHXCV

Test 7

Verdict: ACCEPTED

input
4 2
QNJP
EVJU
XHZF
RXCV

correct output
QEVHZCV

user output
QEVHZCV

Test 8

Verdict: ACCEPTED

input
4 10
QNJP
EVJU
XHZF
RXCV

correct output
QEXRXCV

user output
QEXRXCV

Test 9

Verdict: ACCEPTED

input
4 19
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZCV

user output
QNVJZCV

Test 10

Verdict: ACCEPTED

input
4 20
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZFV

user output
QNVJZFV

Test 11

Verdict: ACCEPTED

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 12

Verdict: ACCEPTED

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 13

Verdict: ACCEPTED

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

Test 15

Verdict: ACCEPTED

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

Test 16

Verdict: ACCEPTED

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...