Submission #559339

#	Time	Username	Problem	Language	Result	Execution time	Memory
559339		LastRonin	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1084 ms	20336 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const ll N = 2e5 + 100;

vector<ll> x[N], e[N];

ll nw[N];
ll px[N], py[N];

long long count_swaps(vector<int> s) {
	ll n = s.size();
	for(int i = 1; i <= n; i++)
		if(s[i - 1] < 0) {
			x[-s[i - 1]].pb(i);	
		}
		else {
			e[s[i - 1]].pb(i);
		}
	ll ans = 0, cur = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < (ll)e[i].size(); j++) {
			if(x[i][j] < e[i][j])
				nw[x[i][j]] = cur, nw[e[i][j]] = -cur;
			else
				nw[x[i][j]] = -cur, nw[e[i][j]] = cur, ans++;
			cur++;
		}
	}
	for(int j = n; j >= 1; j -= 2) {
		ll z = -nw[j];
		ll h = j - 1;
		while(nw[h] != z)
			h--;
		while(h < j - 1) {
			swap(nw[h], nw[h + 1]), h++;					
			ans++;
		}
	}
	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