Submission #364435

# Submission time Handle Problem Language Result Execution time Memory
364435 2021-02-09T07:16:36 Z mosiashvililuka Cat (info1cup19_cat) C++14
100 / 100
657 ms 14884 KB
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,t,tes,f[200009],boo,pi,k[200009],qi,qqi,bo[200009],sup;
pair <int, int> p[3000009],q[200009],qq[200009];
void sw(int qq, int w){
	swap(f[qq],f[w]);
	swap(f[a-qq+1],f[a-w+1]);
}
void dfs(int qq){
	//zx++;
	bo[qq]=t;
	if(f[qq]<=a/2){
		if(bo[f[qq]]==t) return;
		dfs(f[qq]);
	}else{
		zx++;
		qi++;q[qi].first=qq;
		if(bo[a+1-f[qq]]==t) return;
		dfs(a+1-f[qq]);
	}
}
int main(){
	//ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	//cin>>tes;
	scanf("%d\n",&tes);
	for(t=1; t<=tes; t++){
		//cin>>a;
		if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
		for(i=1; i<=a; i++){
			//cin>>f[i];
			if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
		}
		boo=0;
		for(i=1; i<=a/2; i++){
			if(f[i]>a/2){
				boo=1;
				break;
			}
		}
		if(boo==0){
			/*boo=0;
			for(i=1; i<=a/2; i++){
				if(f[a-i+1]-f[i]!=a/2){
					boo=1;
					break;
				}
			}
			if(boo==1){
				cout<<-1<<endl;
				continue;
			}*/
			pi=0;
			for(i=1; i<=a/2; i++){
				k[f[i]]=i;
			}
			for(i=1; i<=a/2; i++){
				if(k[i]==i) continue;
				pi++;
				p[pi].first=k[i];
				p[pi].second=i;
				c=k[i];d=i;
				swap(k[i],k[f[i]]);
				swap(f[c],f[d]);
			}
			for(i=1; i<=pi; i++){
				swap(f[a-p[i].first+1],f[a-p[i].second+1]);
			}
			boo=0;
			for(i=2; i<=a; i++){
				if(f[i]<f[i-1]){
					boo=1;
					break;
				}
			}
			if(boo==1){
//				cout<<-1<<endl;
				printf("-1\n");
				continue;
			}
			//cout<<pi<<" "<<pi<<endl;
			printf("%d %d\n",pi,pi);
			for(i=1; i<=pi; i++){
				//cout<<p[i].first<<" "<<p[i].second<<endl;
				printf("%d %d\n",p[i].first,p[i].second);
			}
			continue;
		}
		boo=0;
		for(i=1; i<=a/2; i++){
			j=a-i+1;
			if(f[i]+f[j]!=a+1){
				boo=1;
				break;
			}
		}
		if(boo==0){
			//printf("%d 0\n",a);
		}else{
			printf("-1\n");
			continue;
		}
		qi=0;qqi=0;
		for(i=1; i<=a/2; i++){
			if(f[i]>f[a-i+1]){
				qi++;
				q[qi].first=i;
				q[qi].second=a-i+1;
			}else{
				/*qqi++;
				qq[qqi].first=a-i+1;
				qq[qqi].second=i;*/
			}
		}
		sup=qi/2;
		if(qi%2==1){
			printf("-1\n");
			continue;
		}else{
			//printf("%d 0\n",a);
		}
		c=0;d=0;e=0;
		qqi=0;pi=0;
		for(i=1; i<=a/2; i++){
			if(bo[i]==t) continue;
			e++;
			zx=0;
			qi=0;
			dfs(i);
			for(j=1; j<=qi/2; j++){
				pi++;
				p[pi].first=q[j].first;
				p[pi].second=a-q[qi-j+1].first+1;
				sw(q[j].first,a-q[qi-j+1].first+1);
			}
			if(qi%2==1){
				qqi++;
				qq[qqi].first=q[qi/2+qi%2].first;
			}
			c+=zx/2;
			d+=zx%2;
		}
		for(i=1; i+1<=qqi; i+=2){
			pi++;
			p[pi].first=qq[i].first;
			p[pi].second=a-qq[i+1].first+1;
			//cout<<p[pi].first<<" l "<<p[pi].second<<endl;
			sw(qq[i].first,a-qq[i+1].first+1);
		}
		sup+=a/2-(e+c-d/2);
		//sample
		for(i=1; i<=a/2; i++){
			//cout<<f[i]<<" ";
			k[f[i]]=i;
		}
		//cout<<endl;
		for(i=1; i<=a/2; i++){
			if(k[i]==i) continue;
			pi++;
			p[pi].first=k[i];
			p[pi].second=i;
			c=k[i];d=i;
			swap(k[i],k[f[i]]);
			swap(f[c],f[d]);
		}
		printf("%d %d\n",sup,pi);
		for(i=1; i<=pi; i++){
			//cout<<p[i].first<<" "<<p[i].second<<endl;
			printf("%d %d\n",p[i].first,p[i].second);
		}
		
		
		//printf("%d 0\n",a/2-(e+c-d/2)+qi/2);
/*		pi=0;
		for(i=1; i+1<=qi; i+=2){
			pi++;
			p[pi].first=q[i].second;p[pi].second=q[i+1].first;
			sw(q[i].second,q[i+1].first);
		}
		//sample
		for(i=1; i<=a/2; i++){
			k[f[i]]=i;
		}
		for(i=1; i<=a/2; i++){
			if(k[i]==i) continue;
			pi++;
			p[pi].first=k[i];
			p[pi].second=i;
			c=k[i];d=i;
			swap(k[i],k[f[i]]);
			swap(f[c],f[d]);
		}
		printf("%d %d\n",sup,pi);
		for(i=1; i<=pi; i++){
			//cout<<p[i].first<<" "<<p[i].second<<endl;
			printf("%d %d\n",p[i].first,p[i].second);
		}*/
	}
	return 0;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d\n",&tes);
      |  ~~~~~^~~~~~~~~~~~~
cat.cpp:28:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |              ~~~~~^~~~~~~~~~~
cat.cpp:28:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |                                     ~~~~~^~~~~~~~~
cat.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |             ~~~~~^~~~~~~~~~~~
cat.cpp:31:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |                                     ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 30 ms 620 KB Output is correct
2 Correct 30 ms 640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 30 ms 620 KB Output is correct
3 Correct 30 ms 640 KB Output is correct
4 Correct 33 ms 620 KB Output is correct
5 Correct 12 ms 512 KB Output is correct
6 Correct 10 ms 492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 30 ms 620 KB Output is correct
2 Correct 30 ms 640 KB Output is correct
3 Correct 629 ms 13036 KB Output is correct
4 Correct 595 ms 11860 KB Output is correct
5 Correct 627 ms 14476 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 30 ms 620 KB Output is correct
3 Correct 30 ms 640 KB Output is correct
4 Correct 33 ms 620 KB Output is correct
5 Correct 12 ms 512 KB Output is correct
6 Correct 10 ms 492 KB Output is correct
7 Correct 629 ms 13036 KB Output is correct
8 Correct 595 ms 11860 KB Output is correct
9 Correct 627 ms 14476 KB Output is correct
10 Correct 627 ms 11372 KB Output is correct
11 Correct 592 ms 9708 KB Output is correct
12 Correct 614 ms 13292 KB Output is correct
13 Correct 657 ms 14884 KB Output is correct
14 Correct 610 ms 12652 KB Output is correct