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

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++;
else
y++;
}
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;
else
l = 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...