Submission #315088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
315088	2020-10-22T02:23:10 Z	Seanliu	Cat (info1cup19_cat)	C++14	24 / 100	1000 ms	7512 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], T;
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 void solve(){
	cin >> N;
	for(int i = 1; i <= N; i++) cin >> arr[i];
	for(int i = 1; i <= N / 2; i++) if(arr[i] + arr[N - i + 1] != N + 1){
		cout << -1 << endl;
		return;
	}
	vector<int> pos = vector<int>();
	vector<pii> ans = vector<pii>();
	for(int i = 1; i <= N / 2; i++) if(arr[i] > arr[N - i + 1]) pos.push_back(i);
	if(pos.size() & 1){ //not sure about this
		cout << -1 << endl;
		return;
	}
	/*
	cout << "have: ";
	for(int x : pos) cout << x << " ";
	cout << endl;
	*/
	for(int i = 0; i < (int)pos.size(); i += 2){
		makeMove(pos[i], N - pos[i + 1] + 1);	
		ans.emplace_back(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.emplace_back(i, nxt);
			//disp();
		}
	}
	cout << ans.size() << " " << ans.size() << endl;
	for(auto [a, b] : ans) cout << a << " " << b << endl;
}

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

Compilation message

cat.cpp: In function 'void solve()':
cat.cpp:59:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |  for(auto [a, b] : ans) cout << a << " " << b << endl;
      |           ^

Subtask #1

5.25 / 15.0

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

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	496 KB	Output is correct
2	Correct	79 ms	764 KB	Output is correct

Subtask #3

8.75 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	18 ms	384 KB	Valid reconstruction
2	Correct	82 ms	496 KB	Output is correct
3	Correct	79 ms	764 KB	Output is correct
4	Partially correct	81 ms	1144 KB	Valid reconstruction
5	Partially correct	32 ms	640 KB	Valid reconstruction
6	Partially correct	27 ms	632 KB	Valid reconstruction

Subtask #4

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	496 KB	Output is correct
2	Correct	79 ms	764 KB	Output is correct
3	Execution timed out	1082 ms	7512 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	18 ms	384 KB	Valid reconstruction
2	Correct	82 ms	496 KB	Output is correct
3	Correct	79 ms	764 KB	Output is correct
4	Partially correct	81 ms	1144 KB	Valid reconstruction
5	Partially correct	32 ms	640 KB	Valid reconstruction
6	Partially correct	27 ms	632 KB	Valid reconstruction
7	Execution timed out	1082 ms	7512 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-