Submission #228745

#	Time	Username	Problem	Language	Result	Execution time	Memory
228745		hhh07	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	251 ms	274680 KiB

shoes

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include "shoes.h"
 
using namespace std;
 
typedef long long ll;
 
vector<ll> t;
 
ll getSum(ll idx){
    ll sum = 0;
    idx++;
    while (idx > 0){
        sum += t[idx];
        idx -= idx & (-idx);
    }
    return sum;
}
 
void updateF(ll n, ll idx, ll val){
    idx++;
    while (idx <= n){
        t[idx] += val;
        idx += idx & (-idx);
    }
}
 
ll count_swaps(vector<int> s){
    ll n = s.size();
    t.assign(n + 1, 0);
    vector<queue<ll>> cnt1(n + 1, queue<ll> ()), cnt2(n + 1, queue<ll> ());
    queue<ll> q;
    for (ll i = n - 1; i >= 0; i--){
        if (s[i] < 0)
            cnt2[-s[i]].push(i);
        else
            cnt1[s[i]].push(i);
    }
    vector<bool> koristen(n, false);
    ll res = 0;
    ll pocetak = n - 2;
    
    for (int i = n - 1; i >= 0; i--){
        if (koristen[i])
            continue;
        ll curr = i;
        
        ll par;
        if (s[i] < 0){
            res++;
            par = cnt1[-s[i]].front();
            cnt1[-s[i]].pop();
            cnt2[-s[i]].pop();
        }
        else{
            par = cnt2[s[i]].front();
            cnt1[s[i]].pop();
            cnt2[s[i]].pop();
        }
        
        koristen[i] = true;
        koristen[par] = true;
        curr += getSum(curr);
        par += getSum(par);
        res += pocetak - par;
        updateF(n, par + 1, -1);
        pocetak -= 2;
    }
    
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15