oj.uz

Submission #519117

# Submission time Handle Problem Language Result Execution time Memory
519117 2022-01-25T17:01:04 Z lucri Cat (info1cup19_cat) C++17
61 / 100
 946 ms 27276 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)
        {
            if(v[i]>n)
            {
                if(poz[i]>n&&poz[i]+i!=2*n+1)
                {
                    ++ans;
                    ans1[ans]=poz[i];
                    ans2[ans]=i;
                    swap(v[i],v[poz[i]]);
                    swap(v[2*n+1-i],v[2*n+1-poz[i]]);
                    swap(poz[v[2*n+1-i]],poz[v[2*n+1-poz[i]]]);
                    swap(poz[v[i]],poz[poz[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]]);
                    ver=0;
                }
            }
        }
        for(int i=1;i<=n;++i)
        {
            while(v[i]!=i)
            {
                ++ans;
                ans1[ans]=v[i];
                ans2[ans]=i;
                swap(v[i],v[v[i]]);
            }
        }
        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 324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 952 KB Output is correct
2 Correct 42 ms 940 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 324 KB Output is correct
2 Correct 40 ms 952 KB Output is correct
3 Correct 42 ms 940 KB Output is correct
4 Partially correct 43 ms 952 KB Valid reconstruction
5 Partially correct 16 ms 664 KB Valid reconstruction
6 Partially correct 20 ms 564 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 952 KB Output is correct
2 Correct 42 ms 940 KB Output is correct
3 Correct 898 ms 25088 KB Output is correct
4 Correct 912 ms 24680 KB Output is correct
5 Correct 909 ms 26612 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 324 KB Output is correct
2 Correct 40 ms 952 KB Output is correct
3 Correct 42 ms 940 KB Output is correct
4 Partially correct 43 ms 952 KB Valid reconstruction
5 Partially correct 16 ms 664 KB Valid reconstruction
6 Partially correct 20 ms 564 KB Valid reconstruction
7 Correct 898 ms 25088 KB Output is correct
8 Correct 912 ms 24680 KB Output is correct
9 Correct 909 ms 26612 KB Output is correct
10 Partially correct 869 ms 23436 KB Valid reconstruction
11 Partially correct 828 ms 22064 KB Valid reconstruction
12 Partially correct 891 ms 26636 KB Valid reconstruction
13 Partially correct 946 ms 27276 KB Valid reconstruction
14 Partially correct 909 ms 26116 KB Valid reconstruction