oj.uz

Submission #755641

# Submission time Handle Problem Language Result Execution time Memory
755641 2023-06-10T13:00:53 Z DJeniUp Cat (info1cup19_cat) C++17
100 / 100
 933 ms 31288 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;
 
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
//#define MOD 998244353
#define INF 10000000000007
#define eps 0.0000000001
 
ll t,n,d[2*N];

queue<pairll>res,g;

vector<ll>v;

int main(){
    
    cin>>t;
    while(t--){
        cin>>n;
        while(res.size()>0)res.pop();
        while(g.size()>0)g.pop();
        v.clear();
        for(int i=1;i<=n;i++){
            cin>>d[i];
        }
        ll fl=0;
        for(int i=1;i<=n/2;i++){
            if(d[i]+d[n-i+1]!=n+1)fl=-1;
            v.pb(i);
        }
        if(fl==-1){
            cout<<-1<<endl;
            continue;
        }
        for(int j=0;j<v.size();j++){
            ll i=v[j];
            //cout<<"! "<<i<<" "<<d[i]<<endl;
            if(i!=d[i]){
                if(d[n-i+1]==i){
                    g.push({i,d[i]});
                }else{
                    res.push({d[i],i});
                    ll x=d[i];
                    ll y=i;
                    swap(d[y],d[x]);
                    swap(d[n-y+1],d[n-x+1]);
                    v.pb(min(i,n-i+1));
                }
            }
        }
        if(g.size()%2==1){
            cout<<-1<<endl;
            continue;
        }
        while(g.size()>0){
            ll m1=g.front().fr;
            ll x=g.front().sc;
            g.pop();
            ll y=g.front().fr;
            g.pop();
            res.push({m1,y});
            res.push({y,x});
        }
        cout<<res.size()<<" "<<res.size()<<endl;
        while(res.size()>0){
            cout<<res.front().fr<<" "<<res.front().sc<<endl;
            res.pop();
        }
    }
 
    return 0;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=0;j<v.size();j++){
      |                     ~^~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 908 KB Output is correct
2 Correct 43 ms 908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 43 ms 908 KB Output is correct
3 Correct 43 ms 908 KB Output is correct
4 Correct 43 ms 1084 KB Output is correct
5 Correct 18 ms 596 KB Output is correct
6 Correct 21 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 908 KB Output is correct
2 Correct 43 ms 908 KB Output is correct
3 Correct 915 ms 28952 KB Output is correct
4 Correct 863 ms 28228 KB Output is correct
5 Correct 933 ms 31056 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 43 ms 908 KB Output is correct
3 Correct 43 ms 908 KB Output is correct
4 Correct 43 ms 1084 KB Output is correct
5 Correct 18 ms 596 KB Output is correct
6 Correct 21 ms 468 KB Output is correct
7 Correct 915 ms 28952 KB Output is correct
8 Correct 863 ms 28228 KB Output is correct
9 Correct 933 ms 31056 KB Output is correct
10 Correct 859 ms 25164 KB Output is correct
11 Correct 893 ms 23676 KB Output is correct
12 Correct 881 ms 30188 KB Output is correct
13 Correct 926 ms 31288 KB Output is correct
14 Correct 847 ms 29920 KB Output is correct