oj.uz

Submission #314579

# Submission time Handle Problem Language Result Execution time Memory
314579 2020-10-20T11:21:13 Z balbit Cat (info1cup19_cat) C++14
100 / 100
 554 ms 14664 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 576 KB Output is correct
2 Correct 34 ms 632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 34 ms 576 KB Output is correct
3 Correct 34 ms 632 KB Output is correct
4 Correct 35 ms 632 KB Output is correct
5 Correct 14 ms 512 KB Output is correct
6 Correct 12 ms 384 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 576 KB Output is correct
2 Correct 34 ms 632 KB Output is correct
3 Correct 489 ms 13008 KB Output is correct
4 Correct 473 ms 11820 KB Output is correct
5 Correct 526 ms 14664 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 34 ms 576 KB Output is correct
3 Correct 34 ms 632 KB Output is correct
4 Correct 35 ms 632 KB Output is correct
5 Correct 14 ms 512 KB Output is correct
6 Correct 12 ms 384 KB Output is correct
7 Correct 489 ms 13008 KB Output is correct
8 Correct 473 ms 11820 KB Output is correct
9 Correct 526 ms 14664 KB Output is correct
10 Correct 513 ms 11936 KB Output is correct
11 Correct 464 ms 9972 KB Output is correct
12 Correct 481 ms 12776 KB Output is correct
13 Correct 554 ms 14360 KB Output is correct
14 Correct 486 ms 12376 KB Output is correct