Submission #228717

#	Time	Username	Problem	Language	Result	Execution time	Memory
228717		hhh07	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	1094 ms	141176 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()/2;
    t.assign(2*n + 1, 0);
    vector<queue<ll>> cnt1(n + 1, queue<ll> ()), cnt2(n + 1, queue<ll> ());
    queue<ll> q;
    for (ll i = 2*n - 1; i >= 0; i--){
        if (s[i] < 0)
            cnt2[-s[i]].push(i);
        else
            cnt1[s[i]].push(i);
    }
    vector<bool> koristen(2*n, false);
    ll res = 0;
    ll pocetak = 2*n - 2;
    
    for (int i = 2*n - 1; i >= 0; i--){
        if (koristen[i])
            continue;
        ll curr = i, 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[curr] = true; koristen[par] = true;
        par += getSum(par);
        curr += getSum(curr);
        res += pocetak - par;
        updateF(2*n, par, -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