oj.uz

답안 #364124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364124 2021-02-08T09:25:23 Z mosiashvililuka Cat (info1cup19_cat) C++14
77.5 / 100
 672 ms 17900 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 q, int w){
	swap(f[q],f[w]);
	swap(f[a-q+1],f[a-w+1]);
}
void dfs(int q){
	//zx++;
	bo[q]=t;
	if(f[q]<=a/2){
		if(bo[f[q]]==t) return;
		dfs(f[q]);
	}else{
		zx++;
		if(bo[a+1-f[q]]==t) return;
		dfs(a+1-f[q]);
	}
}
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;*/
			}
		}
		if(qi%2==1){
			printf("-1\n");
			continue;
		}else{
			//printf("%d 0\n",a);
		}
		c=0;d=0;e=0;
		for(i=1; i<=a/2; i++){
			if(bo[i]==t) continue;
			e++;
			zx=0;
			dfs(i);
			c+=zx/2;
			d+=zx%2;
		}
		sup=a/2-(e+c-d/2)+qi/2;
		//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:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d\n",&tes);
      |  ~~~~~^~~~~~~~~~~~~
cat.cpp:27:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |              ~~~~~^~~~~~~~~~~
cat.cpp:27:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |                                     ~~~~~^~~~~~~~~
cat.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |             ~~~~~^~~~~~~~~~~~
cat.cpp:30:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |                                     ~~~~~^~~~~~~~~~~~~

Subtask #1
10.5 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 364 KB Correct number of moves and valid reconstruction

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 620 KB Output is correct
2 Correct 28 ms 620 KB Output is correct

Subtask #3
17.5 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 364 KB Correct number of moves and valid reconstruction
2 Correct 29 ms 620 KB Output is correct
3 Correct 28 ms 620 KB Output is correct
4 Correct 33 ms 748 KB Correct number of moves and valid reconstruction
5 Correct 13 ms 492 KB Correct number of moves and valid reconstruction
6 Correct 10 ms 492 KB Correct number of moves and valid reconstruction

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 620 KB Output is correct
2 Correct 28 ms 620 KB Output is correct
3 Correct 589 ms 13036 KB Output is correct
4 Correct 569 ms 11884 KB Output is correct
5 Correct 603 ms 14572 KB Output is correct

Subtask #5
24.5 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 364 KB Correct number of moves and valid reconstruction
2 Correct 29 ms 620 KB Output is correct
3 Correct 28 ms 620 KB Output is correct
4 Correct 33 ms 748 KB Correct number of moves and valid reconstruction
5 Correct 13 ms 492 KB Correct number of moves and valid reconstruction
6 Correct 10 ms 492 KB Correct number of moves and valid reconstruction
7 Correct 589 ms 13036 KB Output is correct
8 Correct 569 ms 11884 KB Output is correct
9 Correct 603 ms 14572 KB Output is correct
10 Correct 653 ms 14316 KB Correct number of moves and valid reconstruction
11 Correct 598 ms 12012 KB Correct number of moves and valid reconstruction
12 Correct 616 ms 15212 KB Correct number of moves and valid reconstruction
13 Correct 672 ms 17900 KB Correct number of moves and valid reconstruction
14 Correct 625 ms 15340 KB Correct number of moves and valid reconstruction