oj.uz

Submission #515660

# Submission time Handle Problem Language Result Execution time Memory
515660 2022-01-19T12:36:11 Z Theo830 Cat (info1cup19_cat) C++17
21.25 / 100
 798 ms 8572 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
int main(void){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll arr[n];
        vll a[2];
        ll posa = 0;
        vector<ii>b;
        map<ll,ll>mp;
        f(i,0,n){
            cin>>arr[i];
            if(i < n/2 && arr[i] > n/2){
                posa++;
                b.pb(ii(n + 1 - arr[i],i+1));
                mp[i+1] = n + 1 - arr[i];
            }
            arr[i] = min(arr[i],n + 1 - arr[i]);
            a[i >= n/2].pb(arr[i]);
        }
        reverse(all(a[1]));
        ll res = n / 2;
        bool v[n+5] = {0};
        f(i,0,n/2){
            if(!v[i+1]){
                res--;
                ll pos = i+1;
                while(!v[pos]){
                    v[pos] = true;
                    pos = arr[pos - 1];
                }
            }
        }
        if(a[0] == a[1] && (posa % 2 == 0)){
            cout<<res<<" ";
            cout<<"0\n";
        }
        else{
            cout<<"-1\n";
        }
    }
}

Subtask #1
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Correctly distinguished between possibility and impossibility

Subtask #2
4.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 204 KB Correct number of moves
2 Correct 37 ms 308 KB Correct number of moves

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 38 ms 204 KB Correct number of moves
3 Correct 37 ms 308 KB Correct number of moves
4 Correct 42 ms 308 KB Correctly distinguished between possibility and impossibility
5 Correct 18 ms 308 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 332 KB Correctly distinguished between possibility and impossibility

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 204 KB Correct number of moves
2 Correct 37 ms 308 KB Correct number of moves
3 Correct 682 ms 2392 KB Correct number of moves
4 Correct 699 ms 3468 KB Correct number of moves
5 Correct 725 ms 4268 KB Correct number of moves

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 38 ms 204 KB Correct number of moves
3 Correct 37 ms 308 KB Correct number of moves
4 Correct 42 ms 308 KB Correctly distinguished between possibility and impossibility
5 Correct 18 ms 308 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 332 KB Correctly distinguished between possibility and impossibility
7 Correct 682 ms 2392 KB Correct number of moves
8 Correct 699 ms 3468 KB Correct number of moves
9 Correct 725 ms 4268 KB Correct number of moves
10 Correct 746 ms 2088 KB Correctly distinguished between possibility and impossibility
11 Correct 737 ms 2944 KB Correctly distinguished between possibility and impossibility
12 Correct 783 ms 8572 KB Correctly distinguished between possibility and impossibility
13 Correct 788 ms 8124 KB Correctly distinguished between possibility and impossibility
14 Correct 798 ms 8372 KB Correctly distinguished between possibility and impossibility