oj.uz

Submission #950327

# Submission time Handle Problem Language Result Execution time Memory
950327 2024-03-20T08:17:14 Z pcc Cat (info1cup19_cat) C++17
21.25 / 100
 365 ms 23840 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){
		int nxt = min(arr[now],N+1-arr[now]);
		//cerr<<now<<":"<<nxt<<endl;
		if(ch[now]){
			ch[now] = ch[now]^1;
			ch[nxt] = ch[nxt]^1;
			ans.push_back(pii(now,N+1-nxt));
		}
		else{
			ans.push_back(pii(now,nxt));
		}
		now = nxt;
	};
	//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(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:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 1;i<odds.size();i++){
      |                ~^~~~~~~~~~~~

Subtask #1
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Correctly distinguished between possibility and impossibility

Subtask #2
4.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Correct number of moves
2 Correct 15 ms 3168 KB Correct number of moves

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Correctly distinguished between possibility and impossibility
2 Correct 16 ms 2652 KB Correct number of moves
3 Correct 15 ms 3168 KB Correct number of moves
4 Correct 18 ms 3260 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 2744 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 2652 KB Correctly distinguished between possibility and impossibility

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Correct number of moves
2 Correct 15 ms 3168 KB Correct number of moves
3 Correct 326 ms 22456 KB Correct number of moves
4 Correct 309 ms 21188 KB Correct number of moves
5 Correct 335 ms 23840 KB Correct number of moves

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Correctly distinguished between possibility and impossibility
2 Correct 16 ms 2652 KB Correct number of moves
3 Correct 15 ms 3168 KB Correct number of moves
4 Correct 18 ms 3260 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 2744 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 2652 KB Correctly distinguished between possibility and impossibility
7 Correct 326 ms 22456 KB Correct number of moves
8 Correct 309 ms 21188 KB Correct number of moves
9 Correct 335 ms 23840 KB Correct number of moves
10 Correct 331 ms 20692 KB Correctly distinguished between possibility and impossibility
11 Correct 313 ms 19260 KB Correctly distinguished between possibility and impossibility
12 Correct 327 ms 22652 KB Correctly distinguished between possibility and impossibility
13 Correct 359 ms 23672 KB Correctly distinguished between possibility and impossibility
14 Correct 365 ms 21960 KB Correctly distinguished between possibility and impossibility