Submission #777257

#	Time	Username	Problem	Language	Result	Execution time	Memory
777257		HD1	Cat (info1cup19_cat)	C++14	100 / 100	329 ms	20576 KiB

cat

//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;
void camb(ll i, ll j){
    pos[A[j]]=i;
    pos[A[i]]=j;
    ans.push_back({i,j});
    swap(A[i], A[j]);
    pos[A[n-j+1]]=n-i+1;
    pos[A[n-i+1]]=n-j+1;
    swap(A[n-i+1], A[n-j+1]);
    return;
}
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; i++){
        pos[A[i]]=i;
    }
    ll cont=0;
    ll m=0;
    for(ll i=1;  i<=n/2; i++){
        if(A[i]!=i  &&  A[i]+A[A[i]] != n+1){
            camb(i,pos[i]);
        }
        else if(A[i]+A[A[i]] == n+1){
            if(m==0){
                m=i;
            }
            else{
                camb(m,n-i+1);
                m=0;
            }

        }
    }
    for(ll i=1; i<=n/2; i++){
        if(pos[i]!=i){
            camb(i,A[i]);
        }
    }
    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 (stderr)

cat.cpp: In function 'void solve()':
cat.cpp:54:8: warning: unused variable 'cont' [-Wunused-variable]
   54 |     ll cont=0;
      |        ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35