Submission #315106

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
315106	2020-10-22T02:33:06 Z	Seanliu	Cat (info1cup19_cat)	C++14	51.25 / 100	356 ms	22520 KB

cat

#include <iostream>
#include <vector>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
using namespace std;

const int maxN = 3e6 + 326;

int N, arr[maxN], pos[maxN], T, posc, ansc;
pii ans[maxN];
bool vis[maxN];

inline void makeMove(int i, int j){
	swap(arr[i], arr[j]);
	swap(arr[N - i + 1], arr[N - j + 1]);
}

inline void disp(){
	for(int i = 1; i <= N; i++) cout << arr[i] << " \n"[i == N];
}

inline char readchar() {
    static const size_t bufsize = 65536;
    static char buf[bufsize];
    static char *p = buf, *end = buf;
    if (p == end) end = buf + fread_unlocked(buf, 1, bufsize, stdin), p = buf;
    return *p++;
}

inline void const Read(int & p) {
	p = 0;
	int tmp = 0;
	char c = readchar();
	tmp = !(c^'-');
	while (c < '0' || c > '9') {
		c = readchar();
	}
	while (c >= '0' && c <= '9')
		p = (p<<3)+(p<<1)+(c^48), c = readchar();
	p = tmp?-p:p;
}

inline void solve(){
	Read(N);
	for(int i = 1; i <= N; i++) Read(arr[i]);
	for(int i = 1; i <= N / 2; i++) if(arr[i] + arr[N - i + 1] != N + 1){
		cout << -1 << endl;
		return;
	}
	posc = ansc = 0;
	for(int i = 1; i <= N / 2; i++) if(arr[i] > arr[N - i + 1]) pos[posc++] = i;
	if(posc & 1){ //not sure about this
		cout << -1 << endl;
		return;
	}
	/*
	cout << "have: ";
	for(int x : pos) cout << x << " ";
	cout << endl;
	*/
	for(int i = 0; i < posc; i += 2){
		makeMove(pos[i], N - pos[i + 1] + 1);	
		ans[ansc++] = {pos[i], N - pos[i + 1] + 1};
	}
	//disp();
	fill(vis, vis + N + 1, false);
	for(int i = 1; i <= N / 2; i++){
		while(i != arr[i]){
			int nxt = arr[i];
			makeMove(i, arr[i]);
			ans[ansc++] = {i, nxt};
			//disp();
		}
	}
	cout << ansc << " " << ansc << endl;
	for(int i = 0; i < ansc; i++) cout << ans[i].F << " " << ans[i].S << endl;
}

int main(){
	//ericxiao
	//
	Read(T);
	while(T--){
		solve();
	}
}

Subtask #1

5.25 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	384 KB	Valid reconstruction

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	640 KB	Output is correct
2	Correct	12 ms	640 KB	Output is correct

Subtask #3

8.75 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	384 KB	Valid reconstruction
2	Correct	11 ms	640 KB	Output is correct
3	Correct	12 ms	640 KB	Output is correct
4	Partially correct	17 ms	768 KB	Valid reconstruction
5	Partially correct	6 ms	512 KB	Valid reconstruction
6	Partially correct	5 ms	512 KB	Valid reconstruction

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	640 KB	Output is correct
2	Correct	12 ms	640 KB	Output is correct
3	Correct	270 ms	10104 KB	Output is correct
4	Correct	254 ms	10108 KB	Output is correct
5	Correct	293 ms	12192 KB	Output is correct

Subtask #5

12.25 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	384 KB	Valid reconstruction
2	Correct	11 ms	640 KB	Output is correct
3	Correct	12 ms	640 KB	Output is correct
4	Partially correct	17 ms	768 KB	Valid reconstruction
5	Partially correct	6 ms	512 KB	Valid reconstruction
6	Partially correct	5 ms	512 KB	Valid reconstruction
7	Correct	270 ms	10104 KB	Output is correct
8	Correct	254 ms	10108 KB	Output is correct
9	Correct	293 ms	12192 KB	Output is correct
10	Partially correct	341 ms	20104 KB	Valid reconstruction
11	Partially correct	282 ms	18296 KB	Valid reconstruction
12	Partially correct	296 ms	20856 KB	Valid reconstruction
13	Partially correct	356 ms	22520 KB	Valid reconstruction
14	Partially correct	301 ms	20856 KB	Valid reconstruction