oj.uz

Submission #519127

# Submission time Handle Problem Language Result Execution time Memory
519127 2022-01-25T17:35:58 Z lucri Cat (info1cup19_cat) C++17
100 / 100
 869 ms 12472 KB 
#include <iostream>
using namespace std;
int ans1[6000010],v[3000010],r,n,ans2[6000010],ans,poz[3000010];
int main()
{
    int t;
    cin>>t;
    ++t;
    while(--t)
    {
        int ver=0;
        cin>>n;
        for(int i=1;i<=n;++i)
        {
            cin>>v[i];
            poz[v[i]]=i;
        }
        n/=2;
        for(int i=1;i<=n;++i)
        {
            if(v[i]+v[2*n+1-i]!=2*n+1)
            {
                ver=1;
                break;
            }
            if(v[i]>n)
                ++ver;
        }
        if(ver%2==1)
        {
            cout<<-1<<'\n';
            continue;
        }
        ans=0;
        ver=0;
        for(int i=1;i<=n;++i)
        {
            while(v[i]!=i&&v[i]!=n*2-i+1)
            {
                ++ans;
                ans1[ans]=v[i];
                ans2[ans]=i;
                swap(poz[v[i]],poz[v[v[i]]]);
                swap(poz[v[2*n-i+1]],poz[v[2*n-v[i]+1]]);
                swap(v[2*n-i+1],v[2*n-v[i]+1]);
                swap(v[i],v[v[i]]);
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(v[i]>n)
            {
                if(ver==0)
                    ver=i;
                else
                {
                    ++ans;
                    ans1[ans]=ver;
                    ans2[ans]=2*n-i+1;
                    swap(v[i],v[2*n-ver+1]);
                    swap(v[ver],v[2*n-i+1]);
                    swap(poz[v[i]],poz[v[2*n-ver+1]]);
                    swap(poz[v[ver]],poz[v[2*n-i+1]]);
                    ++ans;
                    ans1[ans]=ver;
                    ans2[ans]=i;
                    swap(v[i],v[ver]);
                    swap(v[2*n-ver+1],v[2*n-i+1]);
                    swap(poz[v[i]],poz[v[ver]]);
                    swap(poz[v[2*n-ver+1]],poz[v[2*n-i+1]]);
                    ver=0;
                }
            }
        }
        cout<<ans<<' '<<ans<<'\n';
        for(int i=1;i<=ans;++i)
            cout<<ans1[i]<<' '<<ans2[i]<<'\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 640 KB Output is correct
2 Correct 38 ms 456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 43 ms 640 KB Output is correct
3 Correct 38 ms 456 KB Output is correct
4 Correct 43 ms 596 KB Output is correct
5 Correct 15 ms 392 KB Output is correct
6 Correct 14 ms 332 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 640 KB Output is correct
2 Correct 38 ms 456 KB Output is correct
3 Correct 869 ms 10172 KB Output is correct
4 Correct 834 ms 9656 KB Output is correct
5 Correct 826 ms 12080 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 43 ms 640 KB Output is correct
3 Correct 38 ms 456 KB Output is correct
4 Correct 43 ms 596 KB Output is correct
5 Correct 15 ms 392 KB Output is correct
6 Correct 14 ms 332 KB Output is correct
7 Correct 869 ms 10172 KB Output is correct
8 Correct 834 ms 9656 KB Output is correct
9 Correct 826 ms 12080 KB Output is correct
10 Correct 811 ms 9428 KB Output is correct
11 Correct 845 ms 7732 KB Output is correct
12 Correct 824 ms 10956 KB Output is correct
13 Correct 840 ms 12472 KB Output is correct
14 Correct 796 ms 10668 KB Output is correct