oj.uz

Submission #515659

# Submission time Handle Problem Language Result Execution time Memory
515659 2022-01-19T12:35:24 Z Theo830 Cat (info1cup19_cat) C++17
15 / 100
 858 ms 10148 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;
        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 12 ms 460 KB Correctly distinguished between possibility and impossibility

Subtask #2
1.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 676 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 668 KB Correctly distinguished between possibility and impossibility

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 460 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 676 KB Correctly distinguished between possibility and impossibility
3 Correct 37 ms 668 KB Correctly distinguished between possibility and impossibility
4 Correct 43 ms 680 KB Correctly distinguished between possibility and impossibility
5 Correct 23 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 460 KB Correctly distinguished between possibility and impossibility

Subtask #4
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 676 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 668 KB Correctly distinguished between possibility and impossibility
3 Correct 730 ms 4296 KB Correctly distinguished between possibility and impossibility
4 Correct 770 ms 5800 KB Correctly distinguished between possibility and impossibility
5 Correct 709 ms 6088 KB Correctly distinguished between possibility and impossibility

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 460 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 676 KB Correctly distinguished between possibility and impossibility
3 Correct 37 ms 668 KB Correctly distinguished between possibility and impossibility
4 Correct 43 ms 680 KB Correctly distinguished between possibility and impossibility
5 Correct 23 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 460 KB Correctly distinguished between possibility and impossibility
7 Correct 730 ms 4296 KB Correctly distinguished between possibility and impossibility
8 Correct 770 ms 5800 KB Correctly distinguished between possibility and impossibility
9 Correct 709 ms 6088 KB Correctly distinguished between possibility and impossibility
10 Correct 788 ms 4372 KB Correctly distinguished between possibility and impossibility
11 Correct 844 ms 4504 KB Correctly distinguished between possibility and impossibility
12 Correct 858 ms 10056 KB Correctly distinguished between possibility and impossibility
13 Correct 814 ms 10148 KB Correctly distinguished between possibility and impossibility
14 Correct 847 ms 9824 KB Correctly distinguished between possibility and impossibility