oj.uz

Submission #476814

# Submission time Handle Problem Language Result Execution time Memory
476814 2021-09-28T15:07:49 Z leaked Cat (info1cup19_cat) C++14
24 / 100
 1000 ms 28684 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;
        map<pii,int>mp;
        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],a[n-i-1]}]=i;
                else mp[{a[n-i-1],a[i]}]=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,n-i-1}];
                do_op(i,j);
//                cout<<"SWAP "<<i+1<<' '<<j+1<<endl;
//                print();
                if(a[j]<a[n-j-1])mp[{a[j],a[n-j-1]}]=j;
                else mp[{a[n-j-1],a[j]}]=j;
            }
        }
        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
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 332 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 968 KB Output is correct
2 Correct 33 ms 968 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 332 KB Valid reconstruction
2 Correct 32 ms 968 KB Output is correct
3 Correct 33 ms 968 KB Output is correct
4 Partially correct 35 ms 1092 KB Valid reconstruction
5 Partially correct 14 ms 588 KB Valid reconstruction
6 Partially correct 12 ms 588 KB Valid reconstruction

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 968 KB Output is correct
2 Correct 33 ms 968 KB Output is correct
3 Execution timed out 1084 ms 28684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 332 KB Valid reconstruction
2 Correct 32 ms 968 KB Output is correct
3 Correct 33 ms 968 KB Output is correct
4 Partially correct 35 ms 1092 KB Valid reconstruction
5 Partially correct 14 ms 588 KB Valid reconstruction
6 Partially correct 12 ms 588 KB Valid reconstruction
7 Execution timed out 1084 ms 28684 KB Time limit exceeded
8 Halted 0 ms 0 KB -