oj.uz

답안 #777232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777232 2023-07-08T19:51:00 Z HD1 Cat (info1cup19_cat) C++14
61 / 100
 337 ms 17344 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=1e7+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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 408 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 656 KB Output is correct
2 Correct 13 ms 604 KB Output is correct

Subtask #3
8.75 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 408 KB Output is correct
2 Correct 13 ms 656 KB Output is correct
3 Correct 13 ms 604 KB Output is correct
4 Partially correct 15 ms 812 KB Valid reconstruction
5 Partially correct 6 ms 584 KB Valid reconstruction
6 Partially correct 5 ms 468 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 656 KB Output is correct
2 Correct 13 ms 604 KB Output is correct
3 Correct 314 ms 14488 KB Output is correct
4 Correct 274 ms 13592 KB Output is correct
5 Correct 298 ms 16692 KB Output is correct

Subtask #5
12.25 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 408 KB Output is correct
2 Correct 13 ms 656 KB Output is correct
3 Correct 13 ms 604 KB Output is correct
4 Partially correct 15 ms 812 KB Valid reconstruction
5 Partially correct 6 ms 584 KB Valid reconstruction
6 Partially correct 5 ms 468 KB Valid reconstruction
7 Correct 314 ms 14488 KB Output is correct
8 Correct 274 ms 13592 KB Output is correct
9 Correct 298 ms 16692 KB Output is correct
10 Partially correct 303 ms 12936 KB Valid reconstruction
11 Partially correct 275 ms 11012 KB Valid reconstruction
12 Partially correct 291 ms 15176 KB Valid reconstruction
13 Partially correct 316 ms 17344 KB Valid reconstruction
14 Partially correct 337 ms 15040 KB Valid reconstruction