oj.uz

Submission #950339

# Submission time Handle Problem Language Result Execution time Memory
950339 2024-03-20T08:35:49 Z pcc Cat (info1cup19_cat) C++17
51.25 / 100
 371 ms 21400 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 3e6+10;
int N;
int arr[mxn];
bitset<mxn> ch;
bitset<mxn> vis;
vector<pii> ans;
vector<pii> psyco;

void change(int a,int b){
	swap(arr[a],arr[b]);
	swap(arr[N-a+1],arr[N-b+1]);
	return;
}

void combine(int a,int b){
	ans.push_back(pii(a,b));
	change(a,b);
	return;
}

void work(int h){
	int now = min(arr[h],N+1-arr[h]);
	while(now != h){
		//cerr<<now<<":"<<h<<":"<<ch[now]<<endl;
		if(arr[h]>arr[N+1-h]){
			swap(arr[h],arr[N+1-h]);
			swap(arr[now],arr[N+1-now]);
			ans.push_back(pii(h,N+1-now));
		}
		else{
			ans.push_back(pii(h,now));
		}
		swap(arr[h],arr[now]);
		swap(arr[N+1-h],arr[N+1-now]);
		now = min(arr[h],N+1-arr[h]);
	};
	//for(int i = 1;i<=N;i++)cerr<<ch[i];cerr<<endl;
	return;
}

void calc(){
	vector<int> odds;
	for(int i = 1;i+i<=N;i++){
		if(vis[i])continue;
		psyco.push_back(pii(i,0));
		int now = i;
		do{
			vis[now] = true;
			psyco.back().sc += ch[now];
			int nxt = min(arr[now],N+1-arr[now]);
			now = nxt;
		}while(now != i);
		if(psyco.back().sc&1){
			odds.push_back(i);
			psyco.pop_back();
		}
	}
	for(int i = 1;i<odds.size();i++){
		combine(odds[0],odds[i]);
	}
	for(int i = 1;i+i<=N;i++){
		ch[i] = false;
		if(arr[i]>arr[N+1-i])ch[i] = true;
	}
	//for(int i = 1;i<=N;i++)cerr<<ch[i];cerr<<endl;
	for(auto &i:psyco)work(i.fs);
	if(!odds.empty())work(odds[0]);
}

void solve(){
	for(int i = 0;i<=N;i++)vis[i] = ch[i] = false;
	psyco.clear();
	ans.clear();
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	int f = 0;
	for(int i = 1;i+i<=N;i++){
		if(arr[i]+arr[N-i+1] != N+1){
			cout<<"-1\n";
			return;
		}
		if(arr[i]>arr[N-i+1]){
			f++;
			ch[i] = true;
		}
	}
	//for(int i = 1;i<=N;i++)cerr<<ch[i];cerr<<endl<<endl;
	if(f&1){
		cout<<"-1\n";
		return;
	}
	calc();
	cout<<ans.size()<<' '<<ans.size()<<'\n';
	for(auto &i:ans)cout<<i.fs<<' '<<i.sc<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
}

Compilation message

cat.cpp: In function 'void calc()':
cat.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 1;i<odds.size();i++){
      |                ~^~~~~~~~~~~~

Subtask #1
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 2392 KB Valid reconstruction

Subtask #2
10.0 / 10.0

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

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 2392 KB Valid reconstruction
2 Correct 15 ms 3172 KB Output is correct
3 Correct 15 ms 3164 KB Output is correct
4 Partially correct 20 ms 3280 KB Valid reconstruction
5 Partially correct 7 ms 2652 KB Valid reconstruction
6 Partially correct 6 ms 2652 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3172 KB Output is correct
2 Correct 15 ms 3164 KB Output is correct
3 Correct 369 ms 20096 KB Output is correct
4 Correct 327 ms 19540 KB Output is correct
5 Correct 345 ms 21400 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 2392 KB Valid reconstruction
2 Correct 15 ms 3172 KB Output is correct
3 Correct 15 ms 3164 KB Output is correct
4 Partially correct 20 ms 3280 KB Valid reconstruction
5 Partially correct 7 ms 2652 KB Valid reconstruction
6 Partially correct 6 ms 2652 KB Valid reconstruction
7 Correct 369 ms 20096 KB Output is correct
8 Correct 327 ms 19540 KB Output is correct
9 Correct 345 ms 21400 KB Output is correct
10 Partially correct 337 ms 18572 KB Valid reconstruction
11 Partially correct 313 ms 17300 KB Valid reconstruction
12 Partially correct 327 ms 19916 KB Valid reconstruction
13 Partially correct 350 ms 21264 KB Valid reconstruction
14 Partially correct 371 ms 19608 KB Valid reconstruction