— Dark mode

Datatähti 2018 loppu

Vaihdot

  • Start: 2018-01-18 12:15:00
  • End: 2018-01-18 17:15:00
CSES - Datatähti 2018 loppu - Results
Submission details
Task:Vaihdot
Sender:Olli
Submission time:2018-01-18 16:00:28 +0200
Language:C++
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.05 s1details
#60.21 s2details
#70.18 s2details
#80.18 s2details
#90.21 s2details
#10ACCEPTED0.05 s2details
#110.42 s3details
#120.41 s3details
#130.45 s3details
#140.42 s3details
#15ACCEPTED0.29 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:223:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                   ^
input/code.cpp:251:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                   ^

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 505;


vector<pair<int, pair<int, int> > > ans;
int table[N][N];
int goal[N][N];

vector<int> colT[N];
vector<int> rowT[N];
vector<int> colG[N];
vector<int> rowG[N];


int firstCT[N];
int firstRT[N];
int firstCG[N];
int firstRG[N];


int revCT[N];
int revRT[N];
int revCG[N];
int revRG[N];

int n;


int testTable[N][N];



void sortRows() {

	for(int r = 1; r <= n; ++r) {
		int toCorrectI = revRT[r];
		int curI = r;
		if(toCorrectI == curI) continue;
		revRG[r] = toCorrectI;
		revRT[toCorrectI] = revRG[r];
		int copy = firstRG[r];
		firstRG[r] = firstRG[toCorrectI];
		firstRG[toCorrectI] = copy;
		ans.push_back(make_pair(1, make_pair(toCorrectI, curI)));
	}


}



void sortCols() {


	for(int c = 1; c <= n; ++c) {
		int toCorrectI = revCT[c];
		int curI = c;
		if(toCorrectI == curI) continue;
		revCG[c] = toCorrectI;
		revCT[toCorrectI] = revCG[c];
		int copy = firstRG[c];
		firstCG[c] = firstCG[toCorrectI];
		firstCG[toCorrectI] = copy;
		ans.push_back(make_pair(2, make_pair(toCorrectI, curI)));
	}

}




int main() {
	cin >> n;
	for(int r = 1; r <= n; ++r) {
		for(int i = 1; i <= n; ++i) {
			cin >> table[r][i];
			testTable[r][i] = table[r][i];
		}
	}

	for(int r = 1; r <= n; ++r) {
		for(int i = 1; i <= n; ++i) {
			cin >> goal[r][i];
		}
	}

	for(int r = 1; r <= n; ++r) {
		for(int x = 1; x <= n; ++x) {
			rowT[r].push_back(table[r][x]);
			rowG[r].push_back(goal[r][x]);
		}
		sort(rowT[r].begin(), rowT[r].end());
		sort(rowG[r].begin(), rowG[r].end());
	}

	for(int c = 1; c <= n; ++c) {
		for(int y = 1; y <= n; ++y) {
			colT[c].push_back(table[y][c]);
			colG[c].push_back(goal[y][c]);
		}
		sort(colT[c].begin(), colT[c].end());
		sort(colG[c].begin(), colG[c].end());
	}

	for(int row = 1; row <= n; ++row) {
		int first = rowT[row][0];
		bool ok = false;
		for(int rows = 1; rows <= n; ++rows) {
			if(rowG[rows][0] == first) {
				ok = true;
				for(int i = 1; i < n; ++i) {
					if(rowT[row][i] != rowG[rows][i]) {
						ok = false;
						break;
					}
				}
				break;
			}
		}
		if(!ok) {
			cout << -1 << "\n";
			return 0;
		}

	}


	for(int col = 1; col <= n; ++col) {
		int first = colT[col][0];
		bool ok = false;
		for(int cols = 1; cols <= n; ++cols) {
			if(colG[cols][0] == first) {
				ok = true;
				for(int i = 1; i < n; ++i) {
					if(colT[col][i] != colG[cols][i]) {
						ok = false;
						break;
					}
				}
			}
		}
		if(!ok) {
			cout << -1 << "\n";
			return 0;
		}

	}


	//There is a solution


	for(int r = 1; r <= n; ++r) {
		firstRT[r] = rowT[r][0];
		firstRG[r] = rowG[r][0];
	}
	for(int c = 1; c <= n; ++c) {
		firstCT[c] = colT[c][0];
		firstCG[c] = colG[c][0];
	}


	for(int r = 1; r <= n; ++r) {
		int target = firstRT[r];
		for(int i = 1; i <= n; ++i) {
			if(firstRG[i] == target) {
				revRT[r] = i;
				break;
			}
		}
	}

	for(int r = 1; r <= n; ++r) {
		int target = firstRG[r];
		for(int i = 1; i <= n; ++i) {
			if(firstRT[i] == target) {
				revRG[r] = i;
				break;
			}
		}
	}
	for(int c = 1; c <= n; ++c) {
		int target = firstCT[c];
		for(int i = 1; i <= n; ++i) {
			if(firstCG[i] == target) {
				revCT[c] = i;
				break;
			}
		}
	}

	for(int c = 1; c <= n; ++c) {
		int target = firstCG[c];
		for(int i = 1; i <= n; ++i) {
			if(firstCT[i] == target) {
				revCG[c] = i;
				break;
			}
		}
	}

	/*cout << "\n\n";

	for(int i = 1; i <= n; ++i) {
		cout << revRT[i] << " ";
	}
	cout << "\n";

	for(int i = 1; i <= n; ++i) {
		cout << revRG[i] << " ";
	}
	cout << "\n";
*/
	sortRows();
	sortCols();
	cout << ans.size() << "\n";

	for(int i = 0; i < ans.size(); ++i) {
		int type = ans[i].first;
		int a = ans[i].second.first;
		int b = ans[i].second.second;
		if(type == 1) {
			int copy;
			for(int j = 1; j <= n; ++j) {
				copy= table[a][j];
				table[a][j] = table[b][j];
				table[b][j] = copy;
			}
		} else {
			int copy;
			for(int j = 1; j <= n; ++j) {
				copy = table[j][a];
				table[j][a] = table[j][b];
				table[j][b] = copy;
			}
		}
	}

	for(int r = 1; r <= n; ++r) {
		for(int c = 1; c <= n; ++c) {
			if(table[r][c] != goal[r][c]) {
				throw exception();
			}
		}
	}
	for(int i = 0; i < ans.size(); ++i) {
		cout << ans[i].first << " " << ans[i].second.first << " " << ans[i].second.second << "\n";
	}
	

		

}




/*

4

3 2 4 1
6 5 8 7
9 11 10 12
16 15 14 13

4 2 1 3
14 15 13 16
8 5 7 6
10 11 12 9











*/

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
3
2 1 7
4 3 6
8 9 5
1 7 2
...
view save

correct output
2
2 1 3
2 1 2
view save

user output
2
2 3 1
2 1 2
view save

Test 2

Group: 1

Verdict: ACCEPTED

input
3
3 7 2
1 5 6
4 8 9
7 3 2
...
view save

correct output
2
1 2 3
2 1 2
view save

user output
2
1 3 2
2 2 1
view save

Test 3

Group: 1

Verdict: ACCEPTED

input
3
3 7 8
4 5 1
6 9 2
3 8 7
...
view save

correct output
1
2 2 3
view save

user output
1
2 3 2
view save

Test 4

Group: 1

Verdict: ACCEPTED

input
3
3 1 8
5 2 6
9 4 7
3 1 8
...
view save

correct output
0
view save

user output
0
view save

Test 5

Group: 1

Verdict: ACCEPTED

input
3
6 5 8
1 2 4
3 7 9
7 9 3
...
view save

correct output
-1
view save

user output
-1
view save

Test 6

Group: 2

Verdict:

input
50
2080 2133 335 2071 1666 1889 4...
view save

correct output
89
1 1 27
1 1 47
1 1 32
1 1 2
...
view save

user output
66
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 7

Group: 2

Verdict:

input
50
59 2140 2044 1095 520 1562 153...
view save

correct output
88
1 1 29
1 1 47
1 1 3
1 1 26
...
view save

user output
64
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 8

Group: 2

Verdict:

input
50
1015 2205 747 1628 2184 61 189...
view save

correct output
94
1 1 17
1 1 30
1 1 15
1 1 3
...
view save

user output
64
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 9

Group: 2

Verdict:

input
50
1936 637 1930 1825 1375 688 23...
view save

correct output
88
1 1 45
1 1 34
1 1 26
1 1 21
...
view save

user output
62
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 10

Group: 2

Verdict: ACCEPTED

input
50
367 944 222 1047 2163 113 1076...
view save

correct output
-1
view save

user output
-1
view save

Test 11

Group: 3

Verdict:

input
500
125877 110081 73003 167540 184...
view save

correct output
986
1 1 222
1 1 325
1 1 203
1 1 73
...
view save

user output
617
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 12

Group: 3

Verdict:

input
500
98396 218927 201855 126130 103...
view save

correct output
983
1 1 80
1 1 125
1 1 242
1 1 85
...
view save

user output
626
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 13

Group: 3

Verdict:

input
500
54508 62242 106667 218403 5323...
view save

correct output
985
1 1 356
1 1 88
1 1 142
1 1 321
...
view save

user output
635
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 14

Group: 3

Verdict:

input
500
108478 62895 206775 78592 2247...
view save

correct output
986
1 1 182
1 1 253
1 1 365
1 1 413
...
view save

user output
642
view save

Error:
terminate called after throwing an instance of 'std::exception'
  what():  std::exception

Test 15

Group: 3

Verdict: ACCEPTED

input
500
96354 155542 19613 222634 1530...
view save

correct output
-1
view save

user output
-1
view save

Tasks

A Tanssiaiset-B Merkkijono-C Tietoverkko-D Vaihdot-E Metsämetro-F Pinopeli-G Alue 50-

Submissions (Olli)

2018-01-19 00:07:36 02018-01-18 17:12:33 02018-01-18 16:00:28 122018-01-18 15:39:19 122018-01-18 14:22:05 0