oj.uz

Submission #515679

# Submission time Handle Problem Language Result Execution time Memory
515679 2022-01-19T12:58:09 Z Theo830 Cat (info1cup19_cat) C++17
40 / 100
 736 ms 4776 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;
        bool b[n+5] = {0};
        f(i,0,n){
            cin>>arr[i];
            if(i < n/2 && arr[i] > n/2){
                posa++;
                b[i+1] = true;
            }
            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 posoi = 0;
                ll pos = i+1;
                while(!v[pos]){
                    v[pos] = true;
                    posoi += b[pos];
                    pos = arr[pos - 1];
                }
                if(posoi % 2 == 1){
                    res++;
                }
            }
        }
        if(a[0] == a[1] && (posa % 2 == 0)){
            cout<<res<<" ";
            cout<<"0\n";
        }
        else{
            cout<<"-1\n";
        }
    }
}

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 204 KB Correct number of moves

Subtask #2
4.0 / 10.0

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

Subtask #3
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 204 KB Correct number of moves
2 Correct 38 ms 300 KB Correct number of moves
3 Correct 38 ms 308 KB Correct number of moves
4 Correct 36 ms 308 KB Correct number of moves
5 Correct 14 ms 304 KB Correct number of moves
6 Correct 12 ms 204 KB Correct number of moves

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 300 KB Correct number of moves
2 Correct 38 ms 308 KB Correct number of moves
3 Correct 713 ms 2528 KB Correct number of moves
4 Correct 710 ms 3772 KB Correct number of moves
5 Correct 694 ms 4388 KB Correct number of moves

Subtask #5
14.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 204 KB Correct number of moves
2 Correct 38 ms 300 KB Correct number of moves
3 Correct 38 ms 308 KB Correct number of moves
4 Correct 36 ms 308 KB Correct number of moves
5 Correct 14 ms 304 KB Correct number of moves
6 Correct 12 ms 204 KB Correct number of moves
7 Correct 713 ms 2528 KB Correct number of moves
8 Correct 710 ms 3772 KB Correct number of moves
9 Correct 694 ms 4388 KB Correct number of moves
10 Correct 701 ms 1224 KB Correct number of moves
11 Correct 655 ms 1564 KB Correct number of moves
12 Correct 736 ms 4740 KB Correct number of moves
13 Correct 711 ms 4664 KB Correct number of moves
14 Correct 731 ms 4776 KB Correct number of moves