CSES - Datatähti 2018 loppu - Results
Submission details
Task:Vaihdot
Sender:Kuha
Submission time:2018-01-18 12:55: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.04 s1details
#6ACCEPTED0.04 s2details
#7ACCEPTED0.04 s2details
#8ACCEPTED0.04 s2details
#9ACCEPTED0.05 s2details
#10ACCEPTED0.04 s2details
#11ACCEPTED0.13 s3details
#12ACCEPTED0.14 s3details
#13ACCEPTED0.13 s3details
#14ACCEPTED0.13 s3details
#15ACCEPTED0.11 s3details

Code

#include <bits/stdc++.h>
#define ll long long
#define N (1<<17)
#define pii pair<int, int>
#define F first
#define S second

using namespace std;

int v[501][501];
int w[501][501];
int n;
pii p[501 * 501];
pii t[501 * 501];

vector<pii> cs;
vector<pii> rs;

void swapr (int a, int b) {
    rs.push_back({a, b});
    for (int i = 1; i <= n; i++) {
        swap(v[a][i], v[b][i]);
        p[v[a][i]] = {a, i};
        p[v[b][i]] = {b, i};
    }
}

void swapc (int a, int b) {
    cs.push_back({a, b});
    for (int i = 1; i <= n; i++) {
        swap(v[i][a], v[i][b]);
        p[v[i][a]] = {i, a};
        p[v[i][b]] = {i, b};
    }
}

int main () {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin>>v[i][j];
            p[v[i][j]] = {i, j};
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin>>w[i][j];
            t[w[i][j]] = {i, j};
        }
    }
    for (int i = 1; i <= n * n; i++) {
        if (p[i].F != t[i].F) {
            swapr(p[i].F, t[i].F);
        }
        if (p[i].S != t[i].S) {
            swapc(p[i].S, t[i].S);
        }
        
        /*for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) cout<<v[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;*/
    }
    for (int i = 1; i <= n * n; i++) {
        if (p[i] != t[i]) {
            //cout<<p[i].F<<" "<<p[i].S<<" "<<i<<endl;
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<(cs.size() + rs.size())<<endl;
    for (pii p : cs) {
        cout<<2<<" "<<p.F<<" "<<p.S<<endl;
    }
    for (pii p : rs) {
        cout<<1<<" "<<p.F<<" "<<p.S<<endl;
    }
}

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 2 1
2 2 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
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 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: 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 8 4
2 36 46
2 25 38
2 43 22
...

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 12 38
2 1 2
2 10 29
2 46 5
...

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 24 9
2 38 10
2 31 8
2 16 27
...

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 4 34
2 19 13
2 12 32
2 26 5
...

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 113 434
2 140 406
2 161 154
2 478 147
...

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 441 223
2 200 177
2 441 359
2 482 267
...

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 332 462
2 482 305
2 135 368
2 486 373
...

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 473 172
2 2 335
2 132 338
2 297 18
...

Test 15

Group: 3

Verdict: ACCEPTED

input
500
96354 155542 19613 222634 1530...

correct output
-1

user output
-1