oj.uz

Submission #315167

# Submission time Handle Problem Language Result Execution time Memory
315167 2020-10-22T03:41:41 Z Seanliu Cat (info1cup19_cat) C++14
51.25 / 100
 346 ms 13816 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)) && 1 > 9){
			int nxt = arr[i], nn = arr[arr[i]];
			ans[ansc++] = {i, nxt};
			makeMove(i, nxt);
			//disp();
		} else 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
5.25 / 15.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 512 KB Valid reconstruction
2 Correct 15 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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 273 ms 10136 KB Output is correct
4 Correct 249 ms 9464 KB Output is correct
5 Correct 294 ms 11768 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 512 KB Valid reconstruction
2 Correct 15 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 10136 KB Output is correct
8 Correct 249 ms 9464 KB Output is correct
9 Correct 294 ms 11768 KB Output is correct
10 Partially correct 340 ms 11384 KB Valid reconstruction
11 Partially correct 277 ms 9336 KB Valid reconstruction
12 Partially correct 313 ms 12024 KB Valid reconstruction
13 Partially correct 346 ms 13816 KB Valid reconstruction
14 Partially correct 299 ms 11836 KB Valid reconstruction