CSES - Datatähti 2015 loppu - Results
Submission details
Task:Ruudukko
Sender:attelaut
Submission time:2015-01-29 16:01:58 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED17
#2ACCEPTED42
#3ACCEPTED41
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.06 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.07 s2details
#11ACCEPTED0.24 s3details
#12ACCEPTED0.15 s3details
#13ACCEPTED0.06 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.07 s3details

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
...

correct output
AAAAAAAAB

user output
AAAAAAAAB

Test 2

Group: 1

Verdict: ACCEPTED

input
5
ABABA
BABAB
ABABA
BABAB
...

correct output
ABABABABA

user output
ABABABABA

Test 3

Group: 1

Verdict: ACCEPTED

input
5
WRYIU
TWLKH
UJMJC
GRDJW
...

correct output
WRWJMDJWK

user output
WRWJMDJWK

Test 4

Group: 1

Verdict: ACCEPTED

input
5
RUEAE
ZYHHW
KDBPD
DXREW
...

correct output
RUEAEWDWX

user output
RUEAEWDWX

Test 5

Group: 1

Verdict: ACCEPTED

input
5
SRGYR
MYDOB
GNOVM
SZOZK
...

correct output
SMGNOOLTU

user output
SMGNOOLTU

Test 6

Group: 2

Verdict: ACCEPTED

input
100
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 7

Group: 2

Verdict: ACCEPTED

input
100
ABABABABABABABABABABABABABABAB...

correct output
ABABABABABABABABABABABABABABAB...

user output
ABABABABABABABABABABABABABABAB...

Test 8

Group: 2

Verdict: ACCEPTED

input
100
FWOVNYKNMMQCNHJGUYPNEDXGVVGONC...

correct output
FWDBDECKBHKIACOVUCJGDJOHAYIBHO...

user output
FWDBDECKBHKIACOVUCJGDJOHAYIBHO...

Test 9

Group: 2

Verdict: ACCEPTED

input
100
ETGCJABWKMAAEOQXWFFYMDJBMNKMQK...

correct output
EAARGLBRLHCDHHBPABHDAJBEEBHQBE...

user output
EAARGLBRLHCDHHBPABHDAJBEEBHQBE...

Test 10

Group: 2

Verdict: ACCEPTED

input
100
GNWMLJNHSBAADUFCSGIZMWHZTVDHNR...

correct output
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC...

user output
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC...

Test 11

Group: 3

Verdict: ACCEPTED

input
500
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 12

Group: 3

Verdict: ACCEPTED

input
500
ABABABABABABABABABABABABABABAB...

correct output
ABABABABABABABABABABABABABABAB...

user output
ABABABABABABABABABABABABABABAB...

Test 13

Group: 3

Verdict: ACCEPTED

input
500
HGADXTSFXYIEMDWMFIVQGHTACFUPYI...

correct output
HGADEJOGAKPJCRAHTABRSDLAVGBFAG...

user output
HGADEJOGAKPJCRAHTABRSDLAVGBFAG...

Test 14

Group: 3

Verdict: ACCEPTED

input
500
SBLNMAZESQVGWAPZYHQJMQTNGMEZWS...

correct output
SBLCAMDHILGIDRCIDUNMMAHFYCENOS...

user output
SBLCAMDHILGIDRCIDUNMMAHFYCENOS...

Test 15

Group: 3

Verdict: ACCEPTED

input
500
AOXYXRYFWPYWQDPWXQITLHQQUAYZAJ...

correct output
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD...

user output
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD...