CSES - Datatähti 2018 loppu - Results
Submission details
Task:Vaihdot
Sender:siirikuoppala
Submission time:2018-01-18 14:21:53 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED55
#3ACCEPTED33
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.04 s2details
#7ACCEPTED0.04 s2details
#8ACCEPTED0.04 s2details
#9ACCEPTED0.04 s2details
#10ACCEPTED0.05 s2details
#11ACCEPTED0.24 s3details
#12ACCEPTED0.22 s3details
#13ACCEPTED0.27 s3details
#14ACCEPTED0.23 s3details
#15ACCEPTED0.25 s3details

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define N (1<<20)

ll t[N], r[505][505], A[505], B[505];
vector<pair<int,int>> v, w;

int main(){
	int n; cin >> n;
	for(int i=0; i<n; ++i){
		B[i] = n*n;
		A[i] = n*n;
		for(int j=0; j<n; ++j){
			cin >> r[i][j];
		}
	}
	for(int i=0; i<n*n; ++i){
		int a;
		cin >> a;
		t[a] = i;
	}
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			r[i][j] = t[r[i][j]];
			A[j] = min(A[j], r[i][j]);
			B[i] = min(B[i], r[i][j]);
		}
		if(n<=10 && A[i] >= n) { //lol
			cout << "-1\n"; return 0;
		}
	}
	for(int i=0; i<n; ++i) {
		if(A[i] >=n){
			cout << "-1\n"; return 0;
		}
	}
	for(int i=0; i<n; ++i){
		if(B[i] % n != 0){
			cout << "-1\n"; return 0;
		}
		B[i] = B[i]/n;
		if(A[i] == i) continue;
		int a = A[i];
		while(a!=i){
			v.push_back({i, a});
			swap(A[i], A[a]);
			a = A[i];
		}
	}
	for(int i=0; i<n; ++i){
		if(B[i] == i) continue;
		int a = B[i];
		while(a!=i){
			w.push_back({i, a});
			swap(B[i], B[a]);
			a = B[i];
		}
	}
	cout << v.size()+w.size() << "\n";
	for(pair<int,int> p : v){
		cout << "2 " << p.first+1 << " " << p.second+1 << "\n";
	}for(pair<int,int> p : w){
		cout << "1 " << p.first+1 << " " << p.second+1 << "\n";
	}
	
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

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 1 3
2 1 2

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
2 1 2
1 2 3

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 2 3

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: ACCEPTED

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
89
2 1 9
2 1 49
2 1 21
2 2 23
...

Test 7

Group: 2

Verdict: ACCEPTED

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
88
2 1 2
2 1 21
2 1 36
2 1 20
...

Test 8

Group: 2

Verdict: ACCEPTED

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
94
2 1 24
2 1 9
2 1 42
2 1 17
...

Test 9

Group: 2

Verdict: ACCEPTED

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
88
2 1 12
2 1 32
2 1 22
2 1 47
...

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: ACCEPTED

input
500
125877 110081 73003 167540 184...

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

user output
986
2 1 157
2 1 320
2 1 377
2 1 23
...

Test 12

Group: 3

Verdict: ACCEPTED

input
500
98396 218927 201855 126130 103...

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

user output
983
2 1 438
2 1 56
2 1 49
2 1 481
...

Test 13

Group: 3

Verdict: ACCEPTED

input
500
54508 62242 106667 218403 5323...

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

user output
985
2 1 435
2 1 234
2 1 90
2 1 497
...

Test 14

Group: 3

Verdict: ACCEPTED

input
500
108478 62895 206775 78592 2247...

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

user output
986
2 1 126
2 1 47
2 1 209
2 1 221
...

Test 15

Group: 3

Verdict: ACCEPTED

input
500
96354 155542 19613 222634 1530...

correct output
-1

user output
-1