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:42:49100
2015-01-29 16:39:3159
2015-01-29 16:15:1359
2015-01-29 12:59:0959
2015-01-29 12:54:4959
2015-01-29 12:39:2859
Task:Ruudukko
Sender:Scintillo
Submission time:2015-01-29 16:42:49
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED17
#2ACCEPTED42
#3ACCEPTED41

Test results

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

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