Submission #1229182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229182		Gray	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	602 ms	147576 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;

struct Fenwick{
    vector<ll> tr;
    ll n, offs;
    Fenwick(ll N){
        n=N+20; offs=10; tr.resize(n+1);
    }
    void add(ll i, ll x){
        i+=offs; for (; i<=n; i+=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        i+=offs; ll sum=0; for (; i; i-=(-i&i)) sum+=tr[i];
        return sum;
    }
};

long long count_swaps(vector<int> s) {
    ll n = s.size(); Fenwick tr(n);
    for (ll i=0; i<n; i++) tr.add(i, 1);
    map<ll, queue<ll>> proc;
    for (ll i=0; i<n; i++){
        proc[s[i]].push(i);
    }
    ll res=0;
    for (ll i=0; i<n; i++){
        ll cur = s[i];
        if (proc[cur].empty() or proc[cur].front()!=i) continue;
        if (cur>0){
            auto ind = proc[-cur].front(); tr.add(ind, -1);
            proc[-cur].pop(); proc[cur].pop();
            res+=tr.get(ind); tr.add(i, -1);
        }else{
            tr.add(i, -1);  auto ind = proc[-cur].front();
            tr.add(ind, -1); proc[-cur].pop();
            proc[cur].pop(); res+=tr.get(ind);
        }
    }

	return res;
}

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