Submission #216209

#	Time	Username	Problem	Language	Result	Execution time	Memory
216209		Pajaraja	Cat (info1cup19_cat)	C++17	50 / 100	1088 ms	27624 KiB

cat

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int p[MAXN],pi[MAXN],n;
bool vi[MAXN];
bool inv(int k) {return p[k]>p[n+1-k];}
int pv(int k) {return min(p[k],p[n+1-k]);}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int c=0,br=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&p[i]);
		fill(vi,vi+MAXN,false);
		bool pr=false;
		for(int i=1;i<=n/2;i++) if(p[i]+p[n+1-i]!=n+1) pr=true;
		for(int i=1;i<=n/2;i++) if(p[i]>p[n+1-i]) c++;
		if(pr || c%2==1) {printf("-1\n"); continue;}
		for(int i=1;i<=n/2;i++) pi[pv(i)]=i;
		vector<int> sw1,sw2;
		for(int i=1;i<=n/2;i++) if(!vi[i])
		{
			int k=pi[i];
			vi[i]=true;
			while(k!=i) 
			{
				
				vi[k]=true; 
				if(inv(k))
				{
					int r=pv(k);
					sw1.push_back(k); sw2.push_back(n+1-r);
					swap(p[k],p[n+1-r]);
					swap(p[n+1-k],p[r]);
				}
				else
				{
					int r=pv(k);
					sw1.push_back(k); sw2.push_back(r);
					swap(p[k],p[r]);
					swap(p[n+1-k],p[n+1-r]);
				}
				k=pi[k];
			}
		}
		vector<int> zs;
		for(int i=1;i<=n/2;i++) if(p[i]>p[n+1-i]) zs.push_back(i);
		for(int i=0;i<zs.size();i+=2) {sw1.push_back(zs[i]); sw2.push_back(n+1-zs[i+1]); sw1.push_back(zs[i]); sw2.push_back(zs[i+1]);}
		printf("%d %d\n",sw1.size(),sw2.size());
		for(int i=0;i<sw1.size();i++) printf("%d %d\n",sw1[i],sw2[i]);
	}
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<zs.size();i+=2) {sw1.push_back(zs[i]); sw2.push_back(n+1-zs[i+1]); sw1.push_back(zs[i]); sw2.push_back(zs[i+1]);}
               ~^~~~~~~~~~
cat.cpp:52:41: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d %d\n",sw1.size(),sw2.size());
                    ~~~~~~~~~~           ^
cat.cpp:52:41: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
cat.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<sw1.size();i++) printf("%d %d\n",sw1[i],sw2[i]);
               ~^~~~~~~~~~~
cat.cpp:14:11: warning: unused variable 'br' [-Wunused-variable]
   int c=0,br=0;
           ^~
cat.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
cat.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
cat.cpp:16:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=1;i<=n;i++) scanf("%d",&p[i]);
                         ~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 35