oj.uz

답안 #315147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
315147 2020-10-22T03:22:26 Z Seanliu Cat (info1cup19_cat) C++14
51.25 / 100
 354 ms 13816 KB 
#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] > N / 2) 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct

Subtask #3
8.75 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 ms 384 KB Valid reconstruction
2 Correct 11 ms 640 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Partially correct 16 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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 273 ms 10124 KB Output is correct
4 Correct 251 ms 9632 KB Output is correct
5 Correct 293 ms 11768 KB Output is correct

Subtask #5
12.25 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 ms 384 KB Valid reconstruction
2 Correct 11 ms 640 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Partially correct 16 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 273 ms 10124 KB Output is correct
8 Correct 251 ms 9632 KB Output is correct
9 Correct 293 ms 11768 KB Output is correct
10 Partially correct 337 ms 11260 KB Valid reconstruction
11 Partially correct 284 ms 9328 KB Valid reconstruction
12 Partially correct 303 ms 11948 KB Valid reconstruction
13 Partially correct 354 ms 13816 KB Valid reconstruction
14 Partially correct 296 ms 12024 KB Valid reconstruction