Submission #312157

#	Time	Username	Problem	Language	Result	Execution time	Memory
312157		zakaF	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1096 ms	70468 KiB

shoes

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
 
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#ifdef LOCAL
	#include </home/linux/debug.h>
	#define dbg(...) cout << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", _print(__VA_ARGS__)
#else
	#define dbg(...)
#endif
#include <queue>
#define sz(x) (int)(x).size()
int cnt(pair<int,int> a,int i)
{
	return (a.first-i)+(a.second-i-1)+(a.first>a.second);
}
bool comp(pair<int,int> &a,pair<int,int> &b)
{
	return cnt(a,0)<cnt(b,0);
}
ll count_swaps(vector<int> x)
{
	queue<pair<int,bool>> a[sz(x)/2+1];
	vector<pair<int,int>> place;
	for(int i=0;i<sz(x);i++)
	{
		if(a[abs(x[i])].empty())
			a[abs(x[i])].push({i,x[i]>0});
		else
		{
			pair<int,bool> p = a[abs(x[i])].front();
			if(p.second!=(x[i]>0))
			{
				a[abs(x[i])].pop();
				if(x[i]>0)
					place.pb({p.first,i});
				else
					place.pb({i,p.first});
			}
			else
			{
				a[abs(x[i])].push({i,x[i]>0});
			}
		}
	}
	sort(rall(place),comp);
	ll ans = 0;
	for(int i = 0;i<sz(x);i+=2)
	{
		pair<int,int> tmp = place.back();
		place.pop_back();
		ans+=(tmp.first-i);
		if(tmp.second<tmp.first)
			tmp.second++;
		ans+=(tmp.second-(i+1));
		for(int j = 0;j<sz(place);j++)
		{
			if(place[j].first<tmp.first)
				place[j].first++;
			if(place[j].first<tmp.second)
				place[j].first++;
			if(place[j].second<tmp.first)
				place[j].second++;
			if(place[j].second<tmp.second)
				place[j].second++;
		}
	}
	return ans;
}

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