Submission #216209

# Submission time Handle Problem Language Result Execution time Memory
216209 2020-03-26T21:46:06 Z Pajaraja Cat (info1cup19_cat) C++17
50 / 100
1000 ms 27624 KB
#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

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]);
                         ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 263 ms 760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 430 ms 1272 KB Output is correct
2 Correct 446 ms 1400 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 263 ms 760 KB Output is correct
2 Correct 430 ms 1272 KB Output is correct
3 Correct 446 ms 1400 KB Output is correct
4 Correct 427 ms 1272 KB Output is correct
5 Correct 184 ms 1016 KB Output is correct
6 Correct 186 ms 760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 430 ms 1272 KB Output is correct
2 Correct 446 ms 1400 KB Output is correct
3 Correct 769 ms 27624 KB Output is correct
4 Correct 799 ms 26524 KB Output is correct
5 Execution timed out 1088 ms 26916 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Correct 263 ms 760 KB Output is correct
2 Correct 430 ms 1272 KB Output is correct
3 Correct 446 ms 1400 KB Output is correct
4 Correct 427 ms 1272 KB Output is correct
5 Correct 184 ms 1016 KB Output is correct
6 Correct 186 ms 760 KB Output is correct
7 Correct 769 ms 27624 KB Output is correct
8 Correct 799 ms 26524 KB Output is correct
9 Execution timed out 1088 ms 26916 KB Time limit exceeded