CSES - Leirikisa 9.12.2021

Submission details
Task:	Ruudukko
Sender:	tonero
Submission time:	2021-12-09 15:37:08 +0200
Language:	C++ (C++17)
Status:	READY
Result:	17

Feedback
group	verdict	score
#1	ACCEPTED	17
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1	details
#2	ACCEPTED	0.01 s	1	details
#3	ACCEPTED	0.01 s	1	details
#4	ACCEPTED	0.01 s	1	details
#5	ACCEPTED	0.01 s	1	details
#6	RUNTIME ERROR	0.08 s	2	details
#7	RUNTIME ERROR	0.09 s	2	details
#8	RUNTIME ERROR	0.09 s	2	details
#9	RUNTIME ERROR	0.09 s	2	details
#10	RUNTIME ERROR	0.09 s	2	details
#11	RUNTIME ERROR	0.09 s	3	details
#12	RUNTIME ERROR	0.08 s	3	details
#13	RUNTIME ERROR	0.09 s	3	details
#14	RUNTIME ERROR	0.09 s	3	details
#15	RUNTIME ERROR	0.09 s	3	details

Code

#include <bits/stdc++.h>

using namespace std;

char arr[500][500] = {{__INT8_MAX__}};

string w[500][500] = {""};

int n;

bool valid(int i){
    return i >= 0 && i < n;
}

bool sF = false;
string shortest = "";
vector<char> shortestVec;

void step(int x, int y, string len, vector<char> jono){
    len += arr[x][y];
    if(!w[x][y].empty() && len.length() >= w[x][y].length() && (len.length() > w[x][y].length() || len >= w[x][y])) return;
    w[x][y] = len;

    jono.emplace_back(arr[x][y]);
    if(x == n-1 && y == n-1){
        shortest = len;
        shortestVec = jono;
        return;
    }

    if(valid(x-1)) step(x-1, y, len, jono);
    if(valid(x+1)) step(x+1, y, len, jono);

    if(valid(y+1)) step(x, y+1, len, jono);
    if(valid(y-1)) step(x, y-1, len, jono);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    char b;
    for (int y = 0; y < n; ++y){
        for (int x = 0; x < n; ++x){
            cin >> b;
            arr[x][y] = b;
        }
    }

    list<tuple<short,short,string, vector<char>>> nxt = {};

    nxt.push_back({0,0,"",{}});

    int x;
    int y;
    string len;
    vector<char> jono;

    while(!nxt.empty()){
        auto elem = nxt.back();
        nxt.pop_back();
        x = get<0>(elem);
        y = get<1>(elem);
        len = get<2>(elem);
        jono = get<3>(elem);

        len += arr[x][y];
        if(!w[x][y].empty() && len.length() >= w[x][y].length() && (len.length() > w[x][y].length() || len >= w[x][y])) continue;
        w[x][y] = len;

        jono.emplace_back(arr[x][y]);
        if(x == n-1 && y == n-1){
            shortest = len;
            shortestVec = jono;
            continue;
        }

        if(valid(x-1)) nxt.emplace_back(x-1, y, len, jono);
        if(valid(x+1)) nxt.emplace_back(x+1, y, len, jono);

        if(valid(y+1)) nxt.emplace_back(x, y+1, len, jono);
        if(valid(y-1)) nxt.emplace_back(x, y-1, len, jono);
    }

    step(0,0, "", {});
    for (const auto &item : shortestVec){
        cout << item;
    }

    flush(std::cout);
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`5 AAAAA AAAAA AAAAA AAAAA ...` view save

correct output
`AAAAAAAAB` view save

user output
`AAAAAAAAB` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`5 ABABA BABAB ABABA BABAB ...` view save

correct output
`ABABABABA` view save

user output
`ABABABABA` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`5 WRYIU TWLKH UJMJC GRDJW ...` view save

correct output
`WRWJMDJWK` view save

user output
`WRWJMDJWK` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`5 RUEAE ZYHHW KDBPD DXREW ...` view save

correct output
`RUEAEWDWX` view save

user output
`RUEAEWDWX` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`5 SRGYR MYDOB GNOVM SZOZK ...` view save

correct output
`SMGNOOLTU` view save

user output
`SMGNOOLTU` view save

Test 6

Group: 2

Verdict: RUNTIME ERROR

input
`100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

correct output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

user output
(empty)

Test 7

Group: 2

Verdict: RUNTIME ERROR

input
`100 ABABABABABABABABABABABABABABAB...` view save

correct output
`ABABABABABABABABABABABABABABAB...` view save

user output
(empty)

Test 8

Group: 2

Verdict: RUNTIME ERROR

input
`100 FWOVNYKNMMQCNHJGUYPNEDXGVVGONC...` view save

correct output
`FWDBDECKBHKIACOVUCJGDJOHAYIBHO...` view save

user output
(empty)

Test 9

Group: 2

Verdict: RUNTIME ERROR

input
`100 ETGCJABWKMAAEOQXWFFYMDJBMNKMQK...` view save

correct output
`EAARGLBRLHCDHHBPABHDAJBEEBHQBE...` view save

user output
(empty)

Test 10

Group: 2

Verdict: RUNTIME ERROR

input
`100 GNWMLJNHSBAADUFCSGIZMWHZTVDHNR...` view save

correct output
`GEGOFRDKBNLLEUOPOEQCEFMTKANLNC...` view save

user output
(empty)

Test 11

Group: 3

Verdict: RUNTIME ERROR

input
`500 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

correct output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

user output
(empty)

Test 12

Group: 3

Verdict: RUNTIME ERROR

input
`500 ABABABABABABABABABABABABABABAB...` view save

correct output
`ABABABABABABABABABABABABABABAB...` view save

user output
(empty)

Test 13

Group: 3

Verdict: RUNTIME ERROR

input
`500 HGADXTSFXYIEMDWMFIVQGHTACFUPYI...` view save

correct output
`HGADEJOGAKPJCRAHTABRSDLAVGBFAG...` view save

user output
(empty)

Test 14

Group: 3

Verdict: RUNTIME ERROR

input
`500 SBLNMAZESQVGWAPZYHQJMQTNGMEZWS...` view save

correct output
`SBLCAMDHILGIDRCIDUNMMAHFYCENOS...` view save

user output
(empty)

Test 15

Group: 3

Verdict: RUNTIME ERROR

input
`500 AOXYXRYFWPYWQDPWXQITLHQQUAYZAJ...` view save

correct output
`AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD...` view save

user output
(empty)

Leirikisa 9.12.2021

Ruudukko

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (tonero)