Submission #754177

#	Time	Username	Problem	Language	Result	Execution time	Memory
754177		inventiontime	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	175 ms	139388 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

typedef long long ll;
typedef vector<int> vi;

struct bit {

    int n;
    vi tree;
    bit(int n) : n(n), tree(n+1) {};

    void add(int pos, int v) {
        for(pos++; pos <= n; pos += pos&-pos)
            tree[pos] += v;
    }

    int pref(int pos) {
        int res = 0;
        for(pos++; pos >= 1; pos -= pos&-pos)
            res += tree[pos];
        return res;
    }

    int query(int a, int b) {
        assert(a <= b);
        return pref(b) - pref(a-1);
    }

};

ll count_swaps(vi s) {

    int n = s.size()/2;
	ll res = 0;

    vector<queue<int>> pos(n*2+1);
    loop(i, n*2)
        pos[n+s[i]].push(i);

    bit bt(n*2);
    loop(i, n*2) bt.add(i, 1);
    
    loop(i, n*2) if(bt.query(i, i) == 1) {
        pos[n+s[i]].pop();
        int x = pos[n-s[i]].front();
        pos[n-s[i]].pop();
        res += bt.query(i+1, x) - 1;
        if(s[i] > 0) res++;
        bt.add(i, -1);
        bt.add(x, -1);
    }

    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