oj.uz

Submission #519119

# Submission time Handle Problem Language Result Execution time Memory
519119 2022-01-25T17:13:50 Z lucri Cat (info1cup19_cat) C++17
40 / 100
 902 ms 12588 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]]);
                }
                else if(poz[i]<=n&&poz[poz[i]]>n&&i+poz[poz[i]]!=n*2+1)
                {
                    ++ans;
                    ans1[ans]=poz[i];
                    ans2[ans]=i;
                    swap(v[i],v[poz[poz[i]]]);
                    swap(v[2*n+1-i],v[2*n+1-poz[poz[i]]]);
                    swap(poz[v[2*n+1-i]],poz[v[2*n+1-poz[poz[i]]]]);
                    swap(poz[v[i]],poz[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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Correct number of moves

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 412 KB Output is correct
2 Correct 38 ms 516 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Correct number of moves
2 Correct 39 ms 412 KB Output is correct
3 Correct 38 ms 516 KB Output is correct
4 Correct 42 ms 548 KB Correctly distinguished between possibility and impossibility
5 Correct 17 ms 528 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 344 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 412 KB Output is correct
2 Correct 38 ms 516 KB Output is correct
3 Correct 902 ms 10164 KB Output is correct
4 Correct 862 ms 9688 KB Output is correct
5 Correct 853 ms 12016 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Correct number of moves
2 Correct 39 ms 412 KB Output is correct
3 Correct 38 ms 516 KB Output is correct
4 Correct 42 ms 548 KB Correctly distinguished between possibility and impossibility
5 Correct 17 ms 528 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 344 KB Correctly distinguished between possibility and impossibility
7 Correct 902 ms 10164 KB Output is correct
8 Correct 862 ms 9688 KB Output is correct
9 Correct 853 ms 12016 KB Output is correct
10 Correct 832 ms 9844 KB Correctly distinguished between possibility and impossibility
11 Correct 789 ms 8244 KB Correctly distinguished between possibility and impossibility
12 Correct 849 ms 11284 KB Correctly distinguished between possibility and impossibility
13 Correct 863 ms 12588 KB Correctly distinguished between possibility and impossibility
14 Correct 880 ms 10904 KB Correctly distinguished between possibility and impossibility