CSES - Datatähti 2018 loppu - Results
Submission details
Task:Vaihdot
Sender:Olli
Submission time:2018-01-18 14:22:05 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.04 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.04 s1details
#4ACCEPTED0.03 s1details
#5ACCEPTED0.05 s1details
#60.04 s2details
#70.05 s2details
#80.03 s2details
#90.04 s2details
#10ACCEPTED0.04 s2details
#110.27 s3details
#120.29 s3details
#130.28 s3details
#140.34 s3details
#15ACCEPTED0.28 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:188: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;


void sortRows() {


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


}



void sortCols() {


	for(int c = 1; c <= n; ++c) {
		int toCorrectI = revCG[c];
		int curI = c;
		if(toCorrectI == curI) continue;
		revCT[c] = toCorrectI;
		revCG[toCorrectI] = revCT[c];
		int copy = firstRT[c];
		firstCT[c] = firstCT[toCorrectI];
		firstCT[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];
		}
	}

	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;
				revRG[i] = r;
				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;
				revCG[i] = c;
				break;
			}
		}
	}

	sortRows();
	sortCols();
	cout << ans.size() << "\n";
	for(int i = 0; i < ans.size(); ++i) {
		cout << ans[i].first << " " << ans[i].second.first << " " << ans[i].second.second << "\n";
	}
	

		

}

Test details

Test 1

Group: 1

Verdict:

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

correct output
2
2 1 3
2 1 2

user output
2
2 2 1
2 1 3

Test 2

Group: 1

Verdict: ACCEPTED

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

correct output
2
1 2 3
2 1 2

user output
2
1 3 2
2 2 1

Test 3

Group: 1

Verdict: ACCEPTED

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

correct output
1
2 2 3

user output
1
2 3 2

Test 4

Group: 1

Verdict: ACCEPTED

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

correct output
0

user output
0

Test 5

Group: 1

Verdict: ACCEPTED

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

correct output
-1

user output
-1

Test 6

Group: 2

Verdict:

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

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

user output
62
1 7 1
1 32 2
1 17 3
1 24 4
...

Test 7

Group: 2

Verdict:

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

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

user output
62
1 16 1
1 46 2
1 47 3
1 45 4
...

Test 8

Group: 2

Verdict:

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

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

user output
64
1 5 1
1 45 2
1 15 3
1 16 4
...

Test 9

Group: 2

Verdict:

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

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

user output
61
1 8 1
1 31 2
1 10 3
1 22 4
...

Test 10

Group: 2

Verdict: ACCEPTED

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

correct output
-1

user output
-1

Test 11

Group: 3

Verdict:

input
500
125877 110081 73003 167540 184...

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

user output
629
1 227 1
1 329 2
1 229 3
1 418 4
...

Test 12

Group: 3

Verdict:

input
500
98396 218927 201855 126130 103...

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

user output
631
1 430 1
1 167 2
1 396 3
1 263 4
...

Test 13

Group: 3

Verdict:

input
500
54508 62242 106667 218403 5323...

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

user output
643
1 358 1
1 500 2
1 209 3
1 159 4
...

Test 14

Group: 3

Verdict:

input
500
108478 62895 206775 78592 2247...

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

user output
633
1 485 1
1 314 2
1 396 3
1 379 4
...

Test 15

Group: 3

Verdict: ACCEPTED

input
500
96354 155542 19613 222634 1530...

correct output
-1

user output
-1