— 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 17:12:33 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.29 s1details
#20.05 s1details
#30.04 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.05 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10ACCEPTED0.05 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15ACCEPTED0.23 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:219:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ans.size(); ++i) { 
                     ^
input/code.cpp:257:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                   ^
input/code.cpp:282:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                   ^
input/code.cpp:297: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];


pair<int, int> locationT[N*N];
pair<int, int> locationG[N*N];

void swapRows(int a, int b) {
	ans.push_back(make_pair(1, make_pair(a, b)));
	int coppy = firstRT[a];
	firstRT[a] = firstRT[b];
	firstRT[b] = coppy;
	for(int i = 1; i <= n; ++i) {
		pair<int, int> copy = locationT[table[a][i]];
		locationT[table[a][i]] = locationT[table[b][i]];
		locationT[table[b][i]] = copy;
	}
}


void swapCols(int a, int b) {
	ans.push_back(make_pair(2, make_pair(a, b)));
	int coppy = firstCT[a];
	firstCT[a] = firstCT[b];
	firstCT[b] = coppy;
	for(int i = 1; i <= n; ++i) {
		pair<int, int> copy = locationT[table[i][a]];
		locationT[table[i][a]] = locationT[table[i][b]];
		locationT[table[i][b]] = copy;
	}
}

/*
void sortRows() {
	for(int times = 1; times <= n; ++times) {
		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 times = 1; times <= n; ++times) {
	
		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];
			locationT[table[r][i]] = make_pair(r, i);
		}
	}

	for(int r = 1; r <= n; ++r) {
		for(int i = 1; i <= n; ++i) {
			cin >> goal[r][i];
			locationG[goal[r][i]] = make_pair(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 i = 1; i <= n*n; ++i) {
		cout << locationT[i].first << " " << locationT[i].second << "\n";
		cout << locationG[i].first << " " << locationG[i].second << "\n";
	}

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

	for(int j = 1; j <= 99999; ++j) {
		for(int i = 1; i <= n*n; ++i) {
			if(locationT[i].first != locationG[i].first) {
				swapRows(locationT[i].first, locationG[i].first);
			}
		}
		for(int i = 1; i <= n*n; ++i) {
			if(locationT[i].second != locationG[i].second) {
				swapCols(locationT[i].second, locationG[i].second);
			}
		}

		bool works = true;
		for(int r = 1; r <= n; ++r) {
			for(int c = 1; c <= n; ++c) {
				if(table[r][c] != goal[r][c]) {
					works = false;
					break;
				}
			}
		}
		if(works) {
			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";
			}
			return 0;
		}
				
	}

	/*for(int t = 1; t <= 1; ++t) {
		for(int i = 1; i <= n; ++i) {
			int k = rowT[i][0];
			if(locationT[k].second != locationG[k].second) {
				swapCols(locationT[k].second, locationG[k].second);
			}
			if(locationT[k].first != locationG[k].first) {
				swapRows(locationT[k].first, locationG[k].first);
			}
		}
	}


	for(int t = 1; t <= 1; ++t) {
		for(int i = 1; i <= n; ++i) {
			int k = colT[i][0];
			if(locationT[k].first != locationG[k].first) {
				swapRows(locationT[k].first, locationG[k].first);
			}
			if(locationT[k].second != locationG[k].second) {
				swapCols(locationT[k].second, locationG[k].second);
			}
		}
	}
	*/
	//cout << locationT[39].first << " " << locationT[39].second << " " << locationG[39].first << " " << locationG[39].second << "\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;
			}
		}
	}


	
	cout << "\n\n\n\n";

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


	cout << "\n\n\n";
	for(int r = 1; r <= n; ++r) {
		for(int c = 1; c <= n; ++c) {
			cout << table[r][c] << " ";
		}
		cout << "\n";
	}



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

		

}




/*

5

3 2 4 1 20
9 11 10 12 22
16 15 14 13 23
17 18 24 19 25
6 5 8 7 21 

4 2 1 3 20
14 15 13 16 23
8 5 7 6 21
10 11 12 9 22
24 18 19 17 25











*/

Test details

Test 1

Group: 1

Verdict:

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
799992




...
view save

Test 2

Group: 1

Verdict:

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




...
view save

Test 3

Group: 1

Verdict:

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




...
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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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