oj.uz

Submission #364114

# Submission time Handle Problem Language Result Execution time Memory
364114 2021-02-08T09:01:59 Z mosiashvililuka Cat (info1cup19_cat) C++14
55 / 100
 628 ms 29164 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];
pair <int, int> p[3000009],q[200009],qq[200009];
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;
		}
		printf("%d 0\n",a/2-(e+c-d/2)+qi/2);
	}
	return 0;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d\n",&tes);
      |  ~~~~~^~~~~~~~~~~~~
cat.cpp:23:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |              ~~~~~^~~~~~~~~~~
cat.cpp:23:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
      |                                     ~~~~~^~~~~~~~~
cat.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |             ~~~~~^~~~~~~~~~~~
cat.cpp:26:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |    if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
      |                                     ~~~~~^~~~~~~~~~~~~

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Correct number of moves

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1092 KB Output is correct
2 Correct 35 ms 1008 KB Output is correct

Subtask #3
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Correct number of moves
2 Correct 29 ms 1092 KB Output is correct
3 Correct 35 ms 1008 KB Output is correct
4 Correct 22 ms 876 KB Correct number of moves
5 Correct 9 ms 620 KB Correct number of moves
6 Correct 7 ms 492 KB Correct number of moves

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1092 KB Output is correct
2 Correct 35 ms 1008 KB Output is correct
3 Correct 628 ms 27884 KB Output is correct
4 Correct 585 ms 26740 KB Output is correct
5 Correct 606 ms 29164 KB Output is correct

Subtask #5
14.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Correct number of moves
2 Correct 29 ms 1092 KB Output is correct
3 Correct 35 ms 1008 KB Output is correct
4 Correct 22 ms 876 KB Correct number of moves
5 Correct 9 ms 620 KB Correct number of moves
6 Correct 7 ms 492 KB Correct number of moves
7 Correct 628 ms 27884 KB Output is correct
8 Correct 585 ms 26740 KB Output is correct
9 Correct 606 ms 29164 KB Output is correct
10 Correct 396 ms 14188 KB Correct number of moves
11 Correct 389 ms 14572 KB Correct number of moves
12 Correct 393 ms 17132 KB Correct number of moves
13 Correct 404 ms 16492 KB Correct number of moves
14 Correct 394 ms 17004 KB Correct number of moves