oj.uz

Submission #777220

# Submission time Handle Problem Language Result Execution time Memory
777220 2023-07-08T19:20:48 Z HD1 Cat (info1cup19_cat) C++14
61 / 100
 330 ms 31600 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]);
            }
        }
    }
    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});
            ll aux=A[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;
}

Compilation message

cat.cpp: In function 'void solve()':
cat.cpp:57:16: warning: unused variable 'aux' [-Wunused-variable]
   57 |             ll aux=A[i];
      |                ^~~

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 532 KB Output is correct
2 Correct 12 ms 540 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 532 KB Output is correct
3 Correct 12 ms 540 KB Output is correct
4 Partially correct 15 ms 1008 KB Valid reconstruction
5 Partially correct 6 ms 632 KB Valid reconstruction
6 Partially correct 5 ms 608 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 532 KB Output is correct
2 Correct 12 ms 540 KB Output is correct
3 Correct 285 ms 14116 KB Output is correct
4 Correct 296 ms 13208 KB Output is correct
5 Correct 295 ms 16312 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 532 KB Output is correct
3 Correct 12 ms 540 KB Output is correct
4 Partially correct 15 ms 1008 KB Valid reconstruction
5 Partially correct 6 ms 632 KB Valid reconstruction
6 Partially correct 5 ms 608 KB Valid reconstruction
7 Correct 285 ms 14116 KB Output is correct
8 Correct 296 ms 13208 KB Output is correct
9 Correct 295 ms 16312 KB Output is correct
10 Partially correct 311 ms 26228 KB Valid reconstruction
11 Partially correct 282 ms 24516 KB Valid reconstruction
12 Partially correct 310 ms 30320 KB Valid reconstruction
13 Partially correct 330 ms 31600 KB Valid reconstruction
14 Partially correct 311 ms 30056 KB Valid reconstruction