Submission #850882

#	Time	Username	Problem	Language	Result	Execution time	Memory
850882		onbert	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	96 ms	18520 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int seg[1000000];

void build(int id, int l, int r) {
    if (l==r) {seg[id] = 0; return;}
    int mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    seg[id] = seg[id*2] + seg[id*2+1];
}

void update(int id, int l, int r, int target) {
    if (l>target||r<target) return;
    if (l==r) {seg[id] = 1; return;}
    // cout << "test3: " << id << endl;
    int mid = (l+r)/2;
    update(id*2, l, mid, target);
    update(id*2+1, mid+1, r, target);
    seg[id] = seg[id*2] + seg[id*2+1];
}

int sum(int id, int l, int r, int findl, int findr) {
    // cout << "test5: " << id << endl;
    if (findl<=l&&r<=findr) return seg[id];
    if (l>findr||r<findl) return 0;
    // cout << "test2: " << id << endl;
    int mid = (l+r)/2;
    return sum(id*2, l, mid, findl, findr) + sum(id*2+1, mid+1, r, findl, findr);
}

int count_swaps(vector<int32_t> a) {
	int n = a.size()/2;
    // cout << n << endl;
    vector<int> left[n+1], right[n+1];
    for (int i=n*2-1;i>=0;i--) {
        if (a[i]<0) left[-a[i]].push_back(i);
        else right[a[i]].push_back(i);
    }
    build(1, 0, n*2-1);
    int ans = 0;
    vector<bool> done(2*n, false);
    int count = 0;
    for (int i=0;i<n*2;i++) {
        if (done[i]) continue;
        // cout << i << endl;
        int sz = abs(a[i]);
        if (a[i]<0) {
            int pos = right[sz].back();
            ans += pos - (count*2+1);
            // cout << "test1: " << ans << " " << pos << endl;
            ans += sum(1, 0, n*2-1, pos+1, n*2-1);
            done[pos] = true;
            update(1, 0, n*2-1, pos);
            // cout << "test4: " << ans << endl;
        } else {
            int pos = left[sz].back();
            ans += pos - count*2;
            // cout << "test1: " << ans << " " << pos << endl;
            ans += sum(1, 0, n*2-1, pos+1, n*2-1);
            done[pos] = true;
            update(1, 0, n*2-1, pos);
            // cout << "test4: " << ans << endl;
        }
        left[sz].pop_back();
        right[sz].pop_back();
        count++;
    }
    return ans;
}

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