Submission #228679

#	Time	Username	Problem	Language	Result	Execution time	Memory
228679		hhh07	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1108 ms	141656 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(4*100001, 0);

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);
    }
}

void build(vector<ll> arr, ll n){
    for (int i = 1; i <= n; i++)
        t[i] = 0;
    for (int i = 0; i < n; i++)
        updateF(n, i, arr[i]);
}

ll count_swaps(vector<int> s){
    int n = s.size()/2;
    
    vector<ll> arr(2*n, 0);
    build(arr, 2*n);
    
    vector<queue<int>> cnt(2*n, queue<int> ());
    queue<int> q;
    vector<bool> koristen(2*n, false);
    for (int i = 2*n - 1; i >= 0; i--){
        if (!koristen[abs(s[i])]){
            q.push(i);
            koristen[abs(s[i])] = true;
        }
        else{
            cnt[abs(s[i])].push((i + 1)*abs(s[i])/s[i]);
            koristen[abs(s[i])] = false;
        }
    }
    
    int res = 0;
    int pocetak = 2*n - 2;
    
    while(!q.empty()){
        int curr = q.front();
        int par =  cnt[abs(s[curr])].front();
        q.pop(); cnt[abs(s[curr])].pop();
        if (par > 0)
            res++;
        else
            par = -par;
        par--;
        par += getSum(par);
        res += pocetak - par;
        updateF(2*n, par, -1);
        pocetak -= 2;
    }
    
    return res;
}

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