Submission #476818

#	Time	Username	Problem	Language	Result	Execution time	Memory
476818		leaked	Cat (info1cup19_cat)	C++14	100 / 100	580 ms	27472 KiB

cat

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)x.size()
using namespace std;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));


signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vec<int> a(n);
        for(auto &z : a) cin>>z,z--;
        vec<pii>vc;
        auto do_op=[&](int i,int j){
            vc.pb({i,j});
            swap(a[i],a[j]);swap(a[n-i-1],a[n-j-1]);
        };
//        for(int i=0;i)
        int ok=1;
        vec<int>mp(n,-1);
        for(int i=0;i<n/2;i++){
            ok&=(a[i]==n-a[n-i-1]-1);
            if(a[i]!=i && a[n-i-1]!=i){
                if(a[i]<a[n-i-1]) mp[a[i]]=i;
                else mp[a[n-i-1]]=n-i-1;
            }
        }
        if(!ok){
            cout<<-1<<'\n';
            continue;
        }
        auto print=[&](){
            cout<<"ARR "<<endl;
            for(auto &z : a) cout<<z<<' ';
            cout<<endl;
        };
        for(int i=0;i<n/2;i++){
            if(a[i]!=i && a[n-i-1]!=i){
//                cerr<<"WHA "<<i<<' '<<n-i-1<<endl;
//                assert(mp.count({i,n-i-1}));
                int j=mp[i];
                assert(j!=-1);
                do_op(i,j);
//                cout<<"SWAP "<<i+1<<' '<<j+1<<endl;
//                print();
                if(a[j]<a[n-j-1])mp[a[j]]=j;
                else mp[a[n-j-1]]=n-j-1;
            }
        }
        vec<int>bad;
        for(int i=0;i<n/2;i++){
            if(a[i]!=i){
                if(a[n-i-1]!=i) assert(false);
                bad.pb(i);
            }
        }
        if(sz(bad)%2){
            cout<<-1<<'\n';
            continue;
        }
        for(int i=0;i<sz(bad);i+=2){
            int x=bad[i],y=bad[i+1];
            do_op(x,n-y-1);
            do_op(x,y);
        }
        for(int i=0;i<n;i++) ok&=(a[i]==i);
        if(!ok) cout<<-1<<'\n';
        else{
            cout<<sz(vc)<<' '<<sz(vc)<<'\n';
            for(auto &z : vc)
                cout<<z.f+1<<' '<<z.s+1<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:40:14: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   40 |         auto print=[&](){
      |              ^~~~~

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