Submission #314579

#	Time	Username	Problem	Language	Result	Execution time	Memory
314579		balbit	Cat (info1cup19_cat)	C++14	100 / 100	554 ms	14664 KiB

cat

#include <bits/stdc++.h>
using namespace std;
#ifndef BALBIT
//#include "grader.h"
#endif

#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x.size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define endl '\n'
#define bug(...)
#endif
#define IOS() ios::sync_with_stdio(0)

#ifdef BALBIT
int kth(int x){bug("k", x); int y; cin>>y; return y;}
int cnt(int x){bug("c", x); int y; cin>>y; return y;}
void say_answer(int x) {bug(x); }
#endif // BALBIT

//mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
//
//void solve(int n) {
//
//    map<int, int> mp;
//    vector<int> p(n);
//    for (int i = 0; i<n; ++i) p[i] = i;
//    shuffle(ALL(p), rng);
//    int qleft = 50;
//    for (int i = 0; i<n && SZ(mp)+1 < qleft-1; ++i) {
//        mp[kth(p[i]+1)]++; --qleft;
//    }
//
//    for (pii p : mp) {
//        int cc = cnt(p.f);
//        if (cc * 3 > n) {
//            say_answer(p.f);
//            return;
//        }
//    }
//    say_answer(-1);
//}
const int maxn = 3e6+6;
int a[maxn];
vector<pii> re;
int n;

void go(int i, int j) {
    if (i == j) return;
    swap(a[i], a[j]);
    swap(a[n-i-1], a[n-j-1]);
    re.pb({i+1,j+1});
}

//#ifdef BALBIT
signed main(){ IOS();
    bug(1,2);
    int t; cin>>t;
    while (t--) {
        cin>>n;
        for (int i = 0; i<n; ++i) {
            cin>>a[i]; --a[i];
        }
        bool inv = 0;
//        bool cancerflip;
        vector<int> at(n/2);
        for (int i = 0; i<n/2; ++i) {
            if (a[i] + a[n-i-1] != n-1) {
                cout<<-1<<endl;
                goto die;
            }
            at[min(a[i], a[n-i-1])]=i;
            inv ^= a[i] > a[n-i-1];
        }
        if (inv) {
            cout<<-1<<endl;
            goto die;
        }

        for (int i = 0; i<n/2; ++i) {
            int j = at[i];
            if (i == j) continue;
            at[min(a[i], a[n-i-1])] = j;
            if (a[j] > a[n-j-1]) {
                // flip!
                go(j, n-i-1);
            }else{
                go(j,i);
            }
        }
        {
            vector<int> nf;
            for (int i = 0; i<n/2; ++i) {
                if (a[i] > a[n-i-1])
                    nf.pb(i);
            }
            assert(SZ(nf) % 2 == 0);
            while (!nf.empty()) {
                int i = nf.back(); nf.pop_back();
                int j = nf.back(); nf.pop_back();
                go(i,n-j-1);
                go(i,j);
            }
        }
        cout<<SZ(re)<<' '<<SZ(re)<<endl;
        for (pii & p : re) {
            cout<<p.f<<' '<<p.s<<endl;
        }
        re.clear();

        die:;


    }
}

//#endif // BALBIT

/*
4
6
2 6 4 3 1 5
10
4 9 6 3 1 10 8 5 2 7
4
4 1 3 2
10
7 8 9 10 5 6 1 2 3 4
*/

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