oj.uz

Submission #476818

# Submission time Handle Problem Language Result Execution time Memory
476818 2021-09-28T15:10:08 Z leaked Cat (info1cup19_cat) C++14
100 / 100
 580 ms 27472 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 24 ms 632 KB Output is correct
3 Correct 24 ms 688 KB Output is correct
4 Correct 35 ms 752 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 11 ms 460 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 632 KB Output is correct
2 Correct 24 ms 688 KB Output is correct
3 Correct 580 ms 13564 KB Output is correct
4 Correct 532 ms 26372 KB Output is correct
5 Correct 573 ms 27460 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 24 ms 632 KB Output is correct
3 Correct 24 ms 688 KB Output is correct
4 Correct 35 ms 752 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 11 ms 460 KB Output is correct
7 Correct 580 ms 13564 KB Output is correct
8 Correct 532 ms 26372 KB Output is correct
9 Correct 573 ms 27460 KB Output is correct
10 Correct 469 ms 24964 KB Output is correct
11 Correct 479 ms 23144 KB Output is correct
12 Correct 512 ms 27056 KB Output is correct
13 Correct 553 ms 27472 KB Output is correct
14 Correct 470 ms 26156 KB Output is correct