oj.uz

Submission #515665

# Submission time Handle Problem Language Result Execution time Memory
515665 2022-01-19T12:40:55 Z Theo830 Cat (info1cup19_cat) C++17
21.25 / 100
 776 ms 8464 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];
                }
            }
        }
        for(auto x:b){
            if(x.S == x.F){
                res += 2;
            }
        }
        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 35 ms 312 KB Correct number of moves
2 Correct 36 ms 304 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 35 ms 312 KB Correct number of moves
3 Correct 36 ms 304 KB Correct number of moves
4 Correct 39 ms 324 KB Correctly distinguished between possibility and impossibility
5 Correct 15 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 35 ms 312 KB Correct number of moves
2 Correct 36 ms 304 KB Correct number of moves
3 Correct 666 ms 2432 KB Correct number of moves
4 Correct 754 ms 3508 KB Correct number of moves
5 Correct 671 ms 4424 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 35 ms 312 KB Correct number of moves
3 Correct 36 ms 304 KB Correct number of moves
4 Correct 39 ms 324 KB Correctly distinguished between possibility and impossibility
5 Correct 15 ms 308 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 332 KB Correctly distinguished between possibility and impossibility
7 Correct 666 ms 2432 KB Correct number of moves
8 Correct 754 ms 3508 KB Correct number of moves
9 Correct 671 ms 4424 KB Correct number of moves
10 Correct 731 ms 2064 KB Correctly distinguished between possibility and impossibility
11 Correct 743 ms 2664 KB Correctly distinguished between possibility and impossibility
12 Correct 776 ms 8464 KB Correctly distinguished between possibility and impossibility
13 Correct 762 ms 8136 KB Correctly distinguished between possibility and impossibility
14 Correct 770 ms 8456 KB Correctly distinguished between possibility and impossibility