oj.uz

답안 #315168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
315168 2020-10-22T03:42:42 Z Seanliu Cat (info1cup19_cat) C++14
61 / 100
 344 ms 12360 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <cassert>
#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(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){
		if(arr[arr[i]] <= N / 2 && ((i + arr[i]) != (N + 1))){
			int nxt = arr[i], nn = arr[arr[i]];
			ans[ansc++] = {i, nxt};
			makeMove(i, nxt);
			//disp();
		}
	}
	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();
	}
	//disp();
	for(int i = 1; i <= N / 2; i++) assert(arr[i] <= N / 2);
	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();
	}
}

Compilation message

cat.cpp: In function 'void solve()':
cat.cpp:58:22: warning: unused variable 'nn' [-Wunused-variable]
   58 |    int nxt = arr[i], nn = arr[arr[i]];
      |                      ^~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct

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 Correct 3 ms 384 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Partially correct 14 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 278 ms 10072 KB Output is correct
4 Correct 247 ms 9448 KB Output is correct
5 Correct 286 ms 11644 KB Output is correct

Subtask #5
12.25 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Partially correct 14 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 278 ms 10072 KB Output is correct
8 Correct 247 ms 9448 KB Output is correct
9 Correct 286 ms 11644 KB Output is correct
10 Partially correct 306 ms 9888 KB Valid reconstruction
11 Partially correct 268 ms 8312 KB Valid reconstruction
12 Partially correct 272 ms 11052 KB Valid reconstruction
13 Partially correct 344 ms 12360 KB Valid reconstruction
14 Partially correct 283 ms 10616 KB Valid reconstruction