oj.uz

Submission #777257

# Submission time Handle Problem Language Result Execution time Memory
777257 2023-07-08T22:33:38 Z HD1 Cat (info1cup19_cat) C++14
100 / 100
 329 ms 20576 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;
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

cat.cpp: In function 'void solve()':
cat.cpp:54:8: warning: unused variable 'cont' [-Wunused-variable]
   54 |     ll cont=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 16 ms 1032 KB Output is correct
2 Correct 13 ms 996 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 16 ms 1032 KB Output is correct
3 Correct 13 ms 996 KB Output is correct
4 Correct 15 ms 1108 KB Output is correct
5 Correct 7 ms 600 KB Output is correct
6 Correct 5 ms 596 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1032 KB Output is correct
2 Correct 13 ms 996 KB Output is correct
3 Correct 312 ms 17192 KB Output is correct
4 Correct 319 ms 17264 KB Output is correct
5 Correct 329 ms 20576 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 16 ms 1032 KB Output is correct
3 Correct 13 ms 996 KB Output is correct
4 Correct 15 ms 1108 KB Output is correct
5 Correct 7 ms 600 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 312 ms 17192 KB Output is correct
8 Correct 319 ms 17264 KB Output is correct
9 Correct 329 ms 20576 KB Output is correct
10 Correct 301 ms 14064 KB Output is correct
11 Correct 270 ms 12524 KB Output is correct
12 Correct 293 ms 17212 KB Output is correct
13 Correct 314 ms 18820 KB Output is correct
14 Correct 291 ms 16708 KB Output is correct