oj.uz

Submission #314577

# Submission time Handle Problem Language Result Execution time Memory
314577 2020-10-20T11:13:55 Z balbit Cat (info1cup19_cat) C++14
51.25 / 100
 551 ms 29444 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];
            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
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 512 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1016 KB Output is correct
2 Correct 32 ms 1024 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 512 KB Valid reconstruction
2 Correct 37 ms 1016 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Partially correct 38 ms 1272 KB Valid reconstruction
5 Partially correct 15 ms 768 KB Valid reconstruction
6 Partially correct 13 ms 640 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1016 KB Output is correct
2 Correct 32 ms 1024 KB Output is correct
3 Correct 498 ms 28012 KB Output is correct
4 Correct 474 ms 26760 KB Output is correct
5 Correct 540 ms 29036 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 512 KB Valid reconstruction
2 Correct 37 ms 1016 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Partially correct 38 ms 1272 KB Valid reconstruction
5 Partially correct 15 ms 768 KB Valid reconstruction
6 Partially correct 13 ms 640 KB Valid reconstruction
7 Correct 498 ms 28012 KB Output is correct
8 Correct 474 ms 26760 KB Output is correct
9 Correct 540 ms 29036 KB Output is correct
10 Partially correct 529 ms 25972 KB Valid reconstruction
11 Partially correct 483 ms 24052 KB Valid reconstruction
12 Partially correct 491 ms 28116 KB Valid reconstruction
13 Partially correct 551 ms 29444 KB Valid reconstruction
14 Partially correct 491 ms 27568 KB Valid reconstruction