oj.uz

Submission #515669

# Submission time Handle Problem Language Result Execution time Memory
515669 2022-01-19T12:45:49 Z Theo830 Cat (info1cup19_cat) C++17
16 / 100
 1000 ms 7028 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;
        set<ll>b;
        f(i,0,n){
            cin>>arr[i];
            if(i < n/2 && arr[i] > n/2){
                posa++;
                b.insert(i+1);
            }
            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.count(pos);
                    pos = arr[pos - 1];
                }
                if(posoi == 1){
                    res++;
                }
            }
        }
        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 11 ms 204 KB Correctly distinguished between possibility and impossibility

Subtask #2
4.0 / 10.0

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

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 304 KB Correct number of moves
3 Correct 38 ms 312 KB Correct number of moves
4 Correct 53 ms 204 KB Correctly distinguished between possibility and impossibility
5 Correct 18 ms 204 KB Correctly distinguished between possibility and impossibility
6 Correct 14 ms 324 KB Correctly distinguished between possibility and impossibility

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 304 KB Correct number of moves
2 Correct 38 ms 312 KB Correct number of moves
3 Correct 706 ms 2444 KB Correct number of moves
4 Correct 685 ms 3468 KB Correct number of moves
5 Correct 683 ms 4220 KB Correct number of moves

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 37 ms 304 KB Correct number of moves
3 Correct 38 ms 312 KB Correct number of moves
4 Correct 53 ms 204 KB Correctly distinguished between possibility and impossibility
5 Correct 18 ms 204 KB Correctly distinguished between possibility and impossibility
6 Correct 14 ms 324 KB Correctly distinguished between possibility and impossibility
7 Correct 706 ms 2444 KB Correct number of moves
8 Correct 685 ms 3468 KB Correct number of moves
9 Correct 683 ms 4220 KB Correct number of moves
10 Correct 872 ms 1844 KB Correctly distinguished between possibility and impossibility
11 Correct 880 ms 2312 KB Correctly distinguished between possibility and impossibility
12 Correct 927 ms 7028 KB Correctly distinguished between possibility and impossibility
13 Execution timed out 1000 ms 6988 KB Time limit exceeded
14 Halted 0 ms 0 KB -