Task: | Ruudukko |
Sender: | Scintillo |
Submission time: | 2015-01-29 16:42:49 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 17 |
#2 | ACCEPTED | 42 |
#3 | ACCEPTED | 41 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.08 s | 2 | details |
#7 | ACCEPTED | 0.07 s | 2 | details |
#8 | ACCEPTED | 0.07 s | 2 | details |
#9 | ACCEPTED | 0.06 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | ACCEPTED | 0.89 s | 3 | details |
#12 | ACCEPTED | 0.90 s | 3 | details |
#13 | ACCEPTED | 0.08 s | 3 | details |
#14 | ACCEPTED | 0.07 s | 3 | details |
#15 | ACCEPTED | 0.08 s | 3 | details |
Compiler report
input/code.cpp: In function 'int rakenna(int, int)': input/code.cpp:155:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized] return paras[x][y] = l; ^
Code
#include <iostream>#include <cstring>#include <unordered_map>using namespace std;char ruudukko[510][510];int paras[510][510];int n;void edista(int& x, int& y){if(paras[x][y] == 1)x++;elsey++;}void tulosta(int x, int y){while(true){cout << ruudukko[x][y];if(x == n - 1 && y == n - 1)break;edista(x, y);}cout << endl;}/*const unsigned int cacheSize = 15463156;char cache[cacheSize];*/unordered_map<int, unordered_map<int, bool>> cache;bool vertaa(int x1, int y1, int x2, int y2){/*unsigned int hash = (x1 + y1 * 500 + x2 * 500 * 500 + y2 * 500 * 500 * 500 * 500) % cacheSize;if(cache[hash])return cache[hash] - 1;*/int hash1 = x1 + 500 * y1;int hash2 = x2 + 500 * y2;if(cache.count(hash1) && cache[hash1].count(hash2))return cache[hash1][hash2];bool ans;if(ruudukko[x1][y1] < ruudukko[x2][y2])ans = true;else if(ruudukko[x1][y1] > ruudukko[x2][y2])ans = false;else if(x1 == n - 1 && y1 == n - 1)ans = true;else if(x2 == n - 1 && y2 == n - 1)ans = false;else{edista(x1, y1);edista(x2, y2);ans = vertaa(x1, y1, x2, y2);}return cache[hash1][hash2] = ans;}bool vertaa(int x, int y){return vertaa(x + 1, y, x, y + 1);}/*bool vertaa(int x, int y){char visited[500 * 500];memset(visited, 0, sizeof(visited));int x1 = x + 1;int y1 = y;int x2 = x;int y2 = y + 1;while(true){if(ruudukko[x1][y1] < ruudukko[x2][y2])return true;else if(ruudukko[x1][y1] > ruudukko[x2][y2])return false;if(x1 == n - 1 && y1 == n - 1)return true;if(x2 == n - 1 && y2 == n - 1)return false;visited[x1 + 500 * y1] = true;visited[x2 + 500 * y2] = true;edista(x1, y1);edista(x2, y2);if(visited[x2 + 500 * y2])return true;if(visited[x1 + 500 * y1])return false;}}*/int rakenna(int x, int y){if(paras[x][y] != 0)return paras[x][y];char a = ruudukko[x + 1][y];char b = ruudukko[x][y + 1];if(a == 0)a = 127;if(b == 0)b = 127;int l;if(a < b){l = 1;rakenna(x + 1, y);}else if(b < a){l = 2;rakenna(x, y + 1);}else if(a != 127){string as, bs;as = rakenna(x + 1, y);bs = rakenna(x, y + 1);if(vertaa(x, y))l = 1;elsel = 2;}return paras[x][y] = l;}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cin >> n;char all = 0;bool hyva = true;for(int j = 0; j < n; j++){for(int i = 0; i < n; i++){cin >> ruudukko[i][j];if(all == 0 || all == ruudukko[i][j]){all = ruudukko[i][j];}else{hyva = false;}}}if(hyva){cout << string(n * 2 - 1, all) << endl;return 0;}rakenna(0, 0);tulosta(0, 0);//vertaa(1, 0);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... |