CSES - Datatähti 2018 loppu - Results
Submission details
Task:Vaihdot
Sender:tuomask
Submission time:2018-01-18 15:42:13 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.14 s1details
#2ACCEPTED0.13 s1details
#3ACCEPTED0.11 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.16 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10--2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Compiler report

input/code.cpp: In function 'std::vector<std::tuple<int, int, int> > f(int, std::vector<std::tuple<int, int, int> >)':
input/code.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (t.size()<m) {
                 ^
input/code.cpp: In function 'int main()':
input/code.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (t.size() == LIMIT) cout << "-1\n";
               ^
input/code.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<t.size(); i++)
                  ^

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<int,int,int> oprtn;
int LIMIT = 8;
ll n;
vector<int> A,B;
void vaihda(int type, int a, int b) {
	if (type) for (int i=0; i<n; i++) swap(A[i*n+a], A[i*n+b]);
	else for (int i=0; i<n; i++) swap(A[a*n+i], A[b*n+i]);
}
vector<oprtn> f(int c, vector<oprtn> op) {
	if (A==B) return op;
	if (c >= LIMIT) {
		op.clear();
		return op;
	}
	int m=INT_MAX;
	vector<oprtn> nop;
	for (int i=0; i<=1; i++) {
		for (int a=0; a<n; a++) {
			for (int b=a+1; b<n; b++) {
				vaihda(i,a,b);
				auto t=f(c+1, op);
				vaihda(i,a,b);
				if (t.size()<m) {
					m=t.size();
					if (m!=INT_MAX) {
						nop = t;
						oprtn n = make_tuple(i+1,a+1,b+1);
						nop.push_back(n);
					}
				}
			}
		}
	}
	return nop;
}
int main() {
	cin >> n;
	A.resize(n*n);
	B.resize(n*n);
	for (int i=0; i<n*n; i++) cin >> A[i];
	for (int i=0; i<n*n; i++) cin >> B[i];
	vector<oprtn> op;
	auto t = f(0, op);
	if (t.size() == LIMIT) cout << "-1\n";
	else {
		cout << t.size() << "\n";
		for (int i=0; i<t.size(); i++)
			cout << get<0>(t[i]) << " " << get<1>(t[i]) << " " << get<2>(t[i]) << "\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 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:

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

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

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

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

Test 10

Group: 2

Verdict:

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

correct output
-1

user output
(empty)

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

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

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

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

Test 15

Group: 3

Verdict:

input
500
96354 155542 19613 222634 1530...

correct output
-1

user output
(empty)