Submission #228697

#	Time	Username	Problem	Language	Result	Execution time	Memory
228697		hhh07	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	1078 ms	75384 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>> cnt(n + 1, queue<ll> ());
    queue<ll> q;
    vector<pair<int, int>> koristen(2*n, make_pair(0, 0));
    for (ll i = 2*n - 1; i >= 0; i--){
        if (s[i] < 0){
            if (koristen[-s[i]].first > 0){
                cnt[-s[i]].push(-(i + 1));
                koristen[-s[i]].first--;
            }
            else{
                q.push(i);
                koristen[-s[i]].second++;
            }
        }
        else{
            if (koristen[s[i]].second > 0){
                cnt[s[i]].push(i + 1);
                koristen[s[i]].second--;
            }
            else{
                q.push(i);
                koristen[s[i]].first++;
            }
        }
    }
    
    ll res = 0;
    ll pocetak = 2*n - 2;
    
    while(!q.empty()){
        ll curr = q.front();
        ll par =  cnt[abs(s[curr])].front();
        q.pop(); cnt[abs(s[curr])].pop();
        if (par > 0)
            res++;
        else
            par = -par;
        par--;
        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