# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
315510 | daniel920712 | Cat (info1cup19_cat) | C++14 | 704 ms | 17132 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int all[3000005];
int where[3000005];
vector < pair < int , int > > ans;
stack < int > how;
int main()
{
int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
scanf("%d",&T);
while(T--)
{
con=0;
t=0;
ok=1;
ans.clear();
scanf("%d",&N);
for(i=1;i<=N;i++)
{
scanf("%d",&all[i]);
where[all[i]]=i;
}
for(i=1;i<=N/2;i++)
{
if(all[i]!=i)
{
x=i;
y=where[i];
if(N-x+1!=y)
{
con++;
swap(all[x],all[y]);
where[all[x]]=x;
where[all[y]]=y;
ans.push_back(make_pair(x,y));
swap(all[N-x+1],all[N-y+1]);
where[all[N-x+1]]=N-x+1;
where[all[N-y+1]]=N-y+1;
if(all[N-i+1]!=N-i+1) break;
}
}
else if(all[N-i+1]!=N-i+1) break;
}
for(i=1;i<=N/2;i++)
{
if(all[i]!=i)
{
x=i;
y=where[i];
if(x==N-y+1)
{
if(how.empty()) how.push(i);
else
{
ans.push_back(make_pair(i,how.top()));
swap(all[i],all[how.top()]);
where[all[i]]=i;
where[all[how.top()]]=how.top();
swap(all[N-i+1],all[N-how.top()+1]);
where[all[N-i+1]]=N-i+1;
where[all[N-how.top()+1]]=N-how.top()+1;
how.pop();
}
}
}
}
for(i=1;i<=N/2;i++)
{
if(all[i]!=i)
{
x=i;
y=where[i];
if(N-x+1!=y)
{
con++;
swap(all[x],all[y]);
where[all[x]]=x;
where[all[y]]=y;
ans.push_back(make_pair(x,y));
swap(all[N-x+1],all[N-y+1]);
where[all[N-x+1]]=N-x+1;
where[all[N-y+1]]=N-y+1;
if(all[N-i+1]!=N-i+1) break;
}
}
else if(all[N-i+1]!=N-i+1) break;
}
con+=tt%2;
for(i=1;i<=N;i++) if(all[i]!=i) ok=0;
if(ok)
{
printf("%d %d\n",ans.size(),ans.size());
for(auto i:ans) printf("%d %d\n",i.first,i.second);
}
else printf("-1\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |