Submission #1064764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064764		Arapak	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	133 ms	144584 KiB

shoes

// Author: Kajetan Ramsza
#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, const pair<auto, auto> &p);
auto& operator<<(auto &os, const auto &v) 
	{ os<<"{"; for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) { os<<", "; } os<<(*it);
	} return os<<"}"; }
auto& operator<<(auto &os, const pair<auto, auto> &p) 
	{ return os<<"("<<p.first<<", "<<p.second<<")"; }

void dbg_out(auto... x) { ((cerr<<' '<<x), ...) << endl; }
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif

int n;
vi s;
vi edge;
vector<ll> num;

struct Tree {
	static constexpr ll unit = 0;
	vector<ll> s; int n;
	Tree(int n_ = 0, ll def = unit) : s(2*n_, def), n(n_) {}
	void update(int pos, ll val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = s[pos * 2] + s[pos * 2 + 1];
	}
	ll query(int b, int e) { // query [b, e)
		ll res = 0;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) res += s[b++];
			if (e % 2) res += s[--e];
		}
		return res;
	}
};

ll count_swaps(vi S) {
	s = S;
	n = sz(s) / 2;
	dbg(s);
	vector<array<queue<int>, 2>> sizes(n+1);
	edge.assign(2*n, -1);
	rep(i,0,2*n) {
		int size = abs(s[i]);
		int right = s[i] > 0;
		if(sizes[size][!right].empty())
			sizes[size][right].push(i);
		else {
			int j = sizes[size][!right].front();
			sizes[size][!right].pop();
			edge[i] = j;
			edge[j] = i;
		}
	}
	dbg(edge);
	num.assign(2*n, 0);
	Tree tree(2*n);
	ll res = 0;
	rep(i,1,2*n) {
		if(edge[i] > i) continue;
		res += tree.query(edge[i], i);
		tree.update(edge[i], 1);
		tree.update(i, 1);
		if(s[i] < 0) res++;
	}
	return res;
}



// 2 3 -4 -2 -3 4 : 3
// 2 -4 -2 4  : +1
// 2 -4 4 -2  : +2

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