oj.uz

Submission #515605

# Submission time Handle Problem Language Result Execution time Memory
515605 2022-01-19T10:33:21 Z Theo830 Cat (info1cup19_cat) C++17
9.75 / 100
 738 ms 6272 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
template <typename T> struct Bit{
    int N;
    vector<T>bit;
    void build(ll n){
        N = n+5;
        f(i,0,N){
            bit.pb(0);
        }
    }
    void upd(ll k,T x){
        while(k < N){
            bit[k] += x;
            k += k & -k;
        }
    }
    T query(ll k){
        T ans = 0;
        while(k >= 1){
            ans += bit[k];
            k -= k & -k;
        }
        return ans;
    }
};
ll c(vll a){
    ll ans = 0;
    Bit<ll>b;
    b.build(a.size() + 5);
    f(j,0,(ll)a.size()){
        ans += j - b.query(a[j]+1);
        b.upd(a[j]+1,1);
    }
    return ans;
}
int main(void){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll arr[n];
        vll a[2];
        ll posa = 0;
        vll b;
        f(i,0,n){
            cin>>arr[i];
            if(i < n/2 && arr[i] > n/2){
                posa++;
                b.pb(n + 1 - arr[i]);
            }
            arr[i] = min(arr[i],n + 1 - arr[i]);
            a[i >= n/2].pb(arr[i]);
        }
        reverse(all(a[1]));
        if(a[0] == a[1] && (posa % 2 == 0)){
            cout<<c(a[0])<<" ";
            cout<<"0\n";
        }
        else{
            cout<<"-1\n";
        }
    }
}

Subtask #1
2.25 / 15.0

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

Subtask #2
1.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 500 KB Correctly distinguished between possibility and impossibility
2 Correct 40 ms 388 KB Correctly distinguished between possibility and impossibility

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 48 ms 500 KB Correctly distinguished between possibility and impossibility
3 Correct 40 ms 388 KB Correctly distinguished between possibility and impossibility
4 Correct 43 ms 452 KB Correctly distinguished between possibility and impossibility
5 Correct 20 ms 456 KB Correctly distinguished between possibility and impossibility
6 Correct 14 ms 428 KB Correctly distinguished between possibility and impossibility

Subtask #4
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 500 KB Correctly distinguished between possibility and impossibility
2 Correct 40 ms 388 KB Correctly distinguished between possibility and impossibility
3 Correct 730 ms 3300 KB Correctly distinguished between possibility and impossibility
4 Correct 722 ms 4704 KB Correctly distinguished between possibility and impossibility
5 Correct 738 ms 5912 KB Correctly distinguished between possibility and impossibility

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 48 ms 500 KB Correctly distinguished between possibility and impossibility
3 Correct 40 ms 388 KB Correctly distinguished between possibility and impossibility
4 Correct 43 ms 452 KB Correctly distinguished between possibility and impossibility
5 Correct 20 ms 456 KB Correctly distinguished between possibility and impossibility
6 Correct 14 ms 428 KB Correctly distinguished between possibility and impossibility
7 Correct 730 ms 3300 KB Correctly distinguished between possibility and impossibility
8 Correct 722 ms 4704 KB Correctly distinguished between possibility and impossibility
9 Correct 738 ms 5912 KB Correctly distinguished between possibility and impossibility
10 Correct 711 ms 2044 KB Correctly distinguished between possibility and impossibility
11 Correct 698 ms 2180 KB Correctly distinguished between possibility and impossibility
12 Incorrect 725 ms 6272 KB Expected int32, but "2472408941" found
13 Halted 0 ms 0 KB -