Submission #1217783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217783		12baater	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	106 ms	150428 KiB

shoes

#include "shoes.h"
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

const long long MAXN = 100000;

ll total = 0;
vector<queue<int> > indices(210000);

struct ST {
	int n;
	vector<int> seg;

	ST (int N) : n(2*N), seg(4*n) {}

	void update(int l, int r) {
		l += n; r += n+1;
		while (l<r) {
			if(l&1) seg[l++]++;
			if(r&1) seg[--r]++;
			l >>= 1;
			r >>= 1;
		}
	}

	ll query(int pos) {
		pos += n;
		ll ret = 0;
		while(pos > 0) {
			ret += seg[pos];
			pos >>= 1;
		}
		return ret;
	}
};

long long count_swaps(vector<int> s) {
	queue<int> neg;
	queue<int> pos;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] > 0) { pos.push(i); continue; }
		neg.push(i);
	}
	ST tree(s.size());
	int origSmall, origBig;
	for(int i = 0; i < s.size()/2; i++) {
		int small = neg.front(); neg.pop();
		origSmall = small;
		small += tree.query(small);
		int big = pos.front(); pos.pop();
		origBig = big;
		big += tree.query(big);
		if(small > big) { swap(small,big); total++; }
		total += big-small-1;
		tree.update(0,max(origSmall,origBig));
	}

	return total;
}

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