Submission #690574

#	Time	Username	Problem	Language	Result	Execution time	Memory
690574		alexdd	Cat (info1cup19_cat)	C++17	25 / 100	937 ms	29372 KiB

cat

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int n;
int p[200001];
int unde[200001];
bool subtask=1;
vector<pair<int,int>> sol;
void da_swap(int x, int y)
{
    sol.push_back({x,y});
    int a=n-x+1,b=n-y+1;
    swap(unde[p[x]], unde[p[y]]);
    swap(p[x], p[y]);

    swap(unde[p[a]], unde[p[b]]);
    swap(p[a], p[b]);
}
void subtask_half()
{
    sol.clear();
    for(int i=1;i<=n/2;i++)
    {
        if(p[i]==i)
            continue;
        da_swap(i, unde[i]);
    }
    bool possible=1;
    for(int i=n/2;i<=n;i++)
        if(p[i]!=i)
        {
            possible=0;
            break;
        }
    if(!possible)
    {
        cout<<-1<<"\n";
    }
    else
    {
        cout<<sol.size()<<" "<<sol.size()<<"\n";
        for(int i=0;i<sol.size();i++)
            cout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        subtask=1;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
            unde[p[i]]=i;
            if(i<=n/2 && p[i]>n/2)
                subtask=0;
        }
        subtask_half();
    }
    return 0;
}

Compilation message (stderr)

cat.cpp: In function 'void subtask_half()':
cat.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0;i<sol.size();i++)
      |                     ~^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 15 / 15
• Subtask 5: 0 / 35