oj.uz

Submission #398499

# Submission time Handle Problem Language Result Execution time Memory
398499 2021-05-04T12:01:37 Z MarcoMeijer Cat (info1cup19_cat) C++14
100 / 100
 527 ms 14692 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<20);

int testCases;
int n, a[MX], ra[MX];

void program() {
    IN(testCases);
    while(testCases--) {
        IN(n);
        RE1(i,n) IN( a[i]);
        RE1(i,n) ra[a[i]] = i;;

        // keeping track of the swaps
        vii ans;
        auto makeSwap = [&](int x, int y) {
            swap(a[x],a[y]);
            swap(a[n-x+1], a[n-y+1]);
            ra[a[x]] = x;
            ra[a[y]] = y;
            ra[a[n-x+1]] = n-x+1;
            ra[a[n-y+1]] = n-y+1;
            ans.pb({x,y});
        };

        RE1(i,n/2) if(ra[i] != i && ra[i] != n-i+1) {
            makeSwap(i,ra[i]);
        }
        
        vi wrongSide;
        RE1(i,n/2) if(a[i] > n/2) wrongSide.pb(i);
        
        // check if it is possible
        bool possible = true;
        RE1(i,n) if(a[i] + a[n-i+1] != n+1) possible = false;
        if(wrongSide.size()%2) possible = false;
        if(!possible) {
            OUTL(-1);
            continue;
        }

        RE(i,wrongSide.size()) {
            makeSwap(wrongSide[i], wrongSide[i+1]);
            makeSwap(wrongSide[i], n-wrongSide[i+1]+1);
            i++;
        }

        OUTLS(ans.size(),ans.size());
        FOR(p,ans) OUTL(p);
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 980 KB Output is correct
2 Correct 23 ms 1020 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 23 ms 980 KB Output is correct
3 Correct 23 ms 1020 KB Output is correct
4 Correct 26 ms 984 KB Output is correct
5 Correct 10 ms 616 KB Output is correct
6 Correct 8 ms 588 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 980 KB Output is correct
2 Correct 23 ms 1020 KB Output is correct
3 Correct 507 ms 13340 KB Output is correct
4 Correct 480 ms 13028 KB Output is correct
5 Correct 514 ms 14692 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 23 ms 980 KB Output is correct
3 Correct 23 ms 1020 KB Output is correct
4 Correct 26 ms 984 KB Output is correct
5 Correct 10 ms 616 KB Output is correct
6 Correct 8 ms 588 KB Output is correct
7 Correct 507 ms 13340 KB Output is correct
8 Correct 480 ms 13028 KB Output is correct
9 Correct 514 ms 14692 KB Output is correct
10 Correct 511 ms 12076 KB Output is correct
11 Correct 458 ms 9996 KB Output is correct
12 Correct 488 ms 12556 KB Output is correct
13 Correct 527 ms 14272 KB Output is correct
14 Correct 483 ms 12208 KB Output is correct