Submission #1064169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064169		Arapak	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	424 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;
vi num;

void add(int l, int r, int x) {
	rep(i,l,r) num[i] += x;
}

set<pii> q;

void swap_elements(int index) {
	q.erase({num[index], index});
	q.erase({num[index+1], index+1});

	if(edge[index] > index) num[index+1]--;
	else num[index]++;
	if(edge[index+1] > index+1) num[index+1]++;
	else num[index]--;

	edge[edge[index]] = index+1;
	edge[edge[index+1]] = index;
	swap(edge[index], edge[index+1]);
	swap(s[index], s[index+1]);
	if(abs(index - edge[index]) > 1) q.insert({num[index], index});
	if(abs(index+1 - edge[index+1]) > 1) q.insert({num[index+1], index+1});
}

ll count_swaps(vi S) {
	s = S;
	n = sz(s) / 2;
	dbg(s);
	vector<array<vi, 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_back(i);
		else {
			int j = sizes[size][!right].back();
			sizes[size][!right].pop_back();
			edge[i] = j;
			edge[j] = i;
		}
	}
	dbg(edge);

	num.assign(2*n, 0);
	rep(i,0,2*n)
		if(edge[i] > i)
			add(i+1,edge[i],1);

	
	rep(i,0,2*n)
		if(abs(i - edge[i]) > 1)
			q.insert({num[i], i});
	dbg(num);
	dbg(q);
	int res = 0;
	while(!q.empty()) {
		int index = (*q.rbegin()).second;
		if(abs(index - edge[index]) == 1) {
			q.erase({num[index], index});
			continue;
		}
		dbg(index, edge[index]);
		if(edge[index] < index) index--;
		swap_elements(index);
		dbg(edge);
		dbg(num);
		dbg(q);
		res++;
	}
	for(int i=0;i<2*n;i+=2)
		if(s[i] > 0) {
			swap(s[i], s[i+1]);
			res++;
		}

	return res;
}

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