oj.uz

Submission #777229

# Submission time Handle Problem Language Result Execution time Memory
777229 2023-07-08T19:42:08 Z HD1 Cat (info1cup19_cat) C++14
61 / 100
 341 ms 17864 KB 
//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ll, ii >tri;
const ll MAX=3*(1e6+100);
const ll mod=1e9+7;
const ll inf=1e9;
ll A[MAX], pos[MAX];
vector<ii> ans;
ll n;
bool sepuede(){
    ll sum=n+1;
    for(ll i=1; i<=n/2; i++){
        if(A[i]+A[sum-i]!=sum) return false;
    }
    ll cont=0;
    for(ll i=1; i<=n/2; i++){
        if(A[i]>n/2)cont++;
    }
    if(cont%2==1) return false;
    return true;
}
void solve(){
    cin>>n;
    for(ll i=1; i<=n; i++){
        cin>>A[i];
    }
    if(!sepuede()){
        cout<<-1<<'\n';
        return;
    }
    for(ll i=1; i<=n/2; i++){
        if(A[i]>n/2){
            if(A[A[i]]<=n/2 and n-i+1!=A[i]){
                ans.push_back({i,A[i]});
                ll aux=A[i];
                swap(A[i],A[A[i]]);
                swap(A[n-i+1],A[n-aux+1]);
            }
        }
    }
    for(ll i=n; i>n/2; i--){
        if(A[i]<=n/2){
            if(A[A[i]]>n/2 and n-i+1!=A[i]){
                ans.push_back({i,A[i]});
                ll aux=A[i];
                swap(A[i],A[A[i]]);
                swap(A[n-i+1],A[n-aux+1]);
            }
        }
    }
    ll j=(n/2);
    for(ll i=1; i<=n/2; i++){
        if(A[i]>n/2){
            while(j+1<=n and A[j+1]>n/2) j++;
            j++;
            ans.push_back({j,i});
            swap(A[i],A[j]);
            swap(A[n-i+1],A[n-j+1]);
        }
    }
    for(ll i=1; i<=n/2; i++){
        pos[A[i]]=i;
    }
    ll cont=0;
    for(ll i=1;  i<=n/2; i++){
        if(A[i]!=i){
            ll a=pos[i];
            ll b=A[i];
            ans.pb({a,i});
            swap(A[pos[i]],A[i]);
            pos[i]=i;
            pos[b]=a;
            cont++;
        }
    }
    /*
    for(ll i=1; i<=n/2; i++){
        cout<<A[i]<<" ";
    }
    cout<<'\n';*/
    cout<<sz(ans)<<" "<<sz(ans)<<'\n';
    for(ii x:ans){
        cout<<x.ff<<" "<<x.ss<<'\n';
    }
    ans.clear();
    return;
}
int main(){
   fastio;
   ll t;
   cin>>t;
   while(t--){
    solve();
   }
   return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1064 KB Output is correct
2 Correct 13 ms 1008 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 13 ms 1064 KB Output is correct
3 Correct 13 ms 1008 KB Output is correct
4 Partially correct 16 ms 1036 KB Valid reconstruction
5 Partially correct 6 ms 596 KB Valid reconstruction
6 Partially correct 5 ms 596 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1064 KB Output is correct
2 Correct 13 ms 1008 KB Output is correct
3 Correct 290 ms 15056 KB Output is correct
4 Correct 292 ms 14136 KB Output is correct
5 Correct 314 ms 17324 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 13 ms 1064 KB Output is correct
3 Correct 13 ms 1008 KB Output is correct
4 Partially correct 16 ms 1036 KB Valid reconstruction
5 Partially correct 6 ms 596 KB Valid reconstruction
6 Partially correct 5 ms 596 KB Valid reconstruction
7 Correct 290 ms 15056 KB Output is correct
8 Correct 292 ms 14136 KB Output is correct
9 Correct 314 ms 17324 KB Output is correct
10 Partially correct 324 ms 13592 KB Valid reconstruction
11 Partially correct 297 ms 11688 KB Valid reconstruction
12 Partially correct 302 ms 15772 KB Valid reconstruction
13 Partially correct 341 ms 17864 KB Valid reconstruction
14 Partially correct 295 ms 15608 KB Valid reconstruction