Code Submission Evaluation System Login

Datatähti 2015 loppu

Start:2015-01-29 12:15:00
End:2015-01-29 17:15:00
 

Tasks | Scoreboard | Statistics


CSES - Datatähti 2015 loppu - Results
History
2015-01-29 16:01:58100
2015-01-29 15:59:4417
2015-01-29 12:43:0417
Task:Ruudukko
Sender:attelaut
Submission time:2015-01-29 16:01:58
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED17
#2ACCEPTED42
#3ACCEPTED41

Test results

testverdicttime (s)group
#1ACCEPTED0.06 / 3.001details
#2ACCEPTED0.06 / 3.001details
#3ACCEPTED0.06 / 3.001details
#4ACCEPTED0.06 / 3.001details
#5ACCEPTED0.06 / 3.001details
#6ACCEPTED0.06 / 3.002details
#7ACCEPTED0.06 / 3.002details
#8ACCEPTED0.06 / 3.002details
#9ACCEPTED0.06 / 3.002details
#10ACCEPTED0.07 / 3.002details
#11ACCEPTED0.24 / 3.003details
#12ACCEPTED0.15 / 3.003details
#13ACCEPTED0.06 / 3.003details
#14ACCEPTED0.06 / 3.003details
#15ACCEPTED0.07 / 3.003details

Code

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

/* string etsi(const vector<vector<char>> &ruudukko, int i, int j, int n) {
    string merkkijono;
    merkkijono += ruudukko[i][j];

    if (i == n - 1 and j == n - 1) {
        return merkkijono;
    } else if (i == n - 1 and j < n - 1) {
        merkkijono += etsi(ruudukko, i, j + 1, n);
    } else if (j == n - 1 and i < n - 1) {
        merkkijono += etsi(ruudukko, i + 1, j, n);
    } else {
        if (ruudukko[i + 1][j] < ruudukko[i][j + 1]) {
            merkkijono += etsi(ruudukko, i + 1, j, n);
        } else if (ruudukko[i + 1][j] > ruudukko[i][j + 1]) {
            merkkijono += etsi(ruudukko, i, j + 1, n);
        } else {
            string m1 = etsi(ruudukko, i, j + 1, n);
            string m2 = etsi(ruudukko, i + 1, j, n);

            if (m1 < m2) {
                merkkijono += m1;
            } else {
                merkkijono += m2;
            }
        }
    }

    return merkkijono;
} */

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<char>> ruudukko(n);

    for (int i = 0; i < n; i++) {
        ruudukko[i] = vector<char>(n);
        for (int j = 0; j < n; j++) {
            char kirjain;
            cin >> kirjain;
            if (kirjain == '\n') {
                j--;
                continue;
            }
            ruudukko[i][j] = kirjain;
        }
    }

    string m;
    set<pair<int, int>> haettavat;
    haettavat.insert(make_pair(0, 0));

    while (true) {
        set<pair<int, int>> uudet;
        char pienin = 'Z';
        for (auto p : haettavat) {
            if (p.first >= n or p.second >= n) {
                continue;
            }

            char merkki = ruudukko[p.first][p.second];
            if (merkki < pienin) {
                pienin = merkki;
                uudet.clear();
            }

            if (merkki == pienin) {
                if (p.first + 1 < n) {
                    uudet.insert(make_pair(p.first + 1, p.second));
                }

                if (p.second + 1 < n) {
                    uudet.insert(make_pair(p.first, p.second + 1));
                }
            }
        }

        m += pienin;

        if (uudet.size() == 0) {
            break;
        }

        haettavat = uudet;
    }

    cout << m << "\n";

    return 0;
}

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

input
100
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 7

Group: 2

Verdict: ACCEPTED

input
100
ABABABABABABABABABABABABABABAB...
view   save

correct output
ABABABABABABABABABABABABABABAB...
view   save

user output
ABABABABABABABABABABABABABABAB...
view   save

Test 8

Group: 2

Verdict: ACCEPTED

input
100
FWOVNYKNMMQCNHJGUYPNEDXGVVGONC...
view   save

correct output
FWDBDECKBHKIACOVUCJGDJOHAYIBHO...
view   save

user output
FWDBDECKBHKIACOVUCJGDJOHAYIBHO...
view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
100
ETGCJABWKMAAEOQXWFFYMDJBMNKMQK...
view   save

correct output
EAARGLBRLHCDHHBPABHDAJBEEBHQBE...
view   save

user output
EAARGLBRLHCDHHBPABHDAJBEEBHQBE...
view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
100
GNWMLJNHSBAADUFCSGIZMWHZTVDHNR...
view   save

correct output
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC...
view   save

user output
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC...
view   save

Test 11

Group: 3

Verdict: ACCEPTED

input
500
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 12

Group: 3

Verdict: ACCEPTED

input
500
ABABABABABABABABABABABABABABAB...
view   save

correct output
ABABABABABABABABABABABABABABAB...
view   save

user output
ABABABABABABABABABABABABABABAB...
view   save

Test 13

Group: 3

Verdict: ACCEPTED

input
500
HGADXTSFXYIEMDWMFIVQGHTACFUPYI...
view   save

correct output
HGADEJOGAKPJCRAHTABRSDLAVGBFAG...
view   save

user output
HGADEJOGAKPJCRAHTABRSDLAVGBFAG...
view   save

Test 14

Group: 3

Verdict: ACCEPTED

input
500
SBLNMAZESQVGWAPZYHQJMQTNGMEZWS...
view   save

correct output
SBLCAMDHILGIDRCIDUNMMAHFYCENOS...
view   save

user output
SBLCAMDHILGIDRCIDUNMMAHFYCENOS...
view   save

Test 15

Group: 3

Verdict: ACCEPTED

input
500
AOXYXRYFWPYWQDPWXQITLHQQUAYZAJ...
view   save

correct output
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD...
view   save

user output
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD...
view   save