Submission #414034

#	Time	Username	Problem	Language	Result	Execution time	Memory
414034		asfd221	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	126 ms	22432 KiB

shoes

#include <bits/stdc++.h>
#define INF (ll)(2e9)
#define MD (998244353)
#define pb push_back
#define mp make_pair
#define ft first
#define sd second

using namespace std;
using ll = long long;
using cd = complex<double>;
using ul = unsigned long;

void f_io () { ios_base :: sync_with_stdio (false); cin.tie (nullptr);
 cout.tie (nullptr);
}

const ll MAX = 3e5 + 5, MOD = 998244353, M = 3e6;

ll gc (ll a, ll b) {
	if (!a || !b) {
		return max (a, b);
	}
	ll r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

ll mult (ll a, ll b) {
	return ((a % MOD)  * 1LL * (b % MOD)) % MOD;
}

ll add (ll a, ll b) {
	b = (b % MOD + MOD) % MOD;
	return (a + b) % MOD;
}

ll pw (ll a, ll b) {
	if (b < 0) {
		return 1;
	}
	ll r = 1;
	while (b) {
		if (b & 1) {
			r = mult (a, r);
		}
		b >>= 1;
		a = mult (a, a);
	}
	return r;
}
int f[MAX];

void up (int x, int v) {
	x++;
	for (int i = x; i < MAX; i += i & (-i)) {
		f[i] += v;
	}
}

ll an (int x) {
	ll s = 0;
	x++;
	for (int i = x; i; i -= i & (-i)) {
		s += f[i];
	}
	return s;
}

ll inv (vector<int> v) {
	for (ll i = 0; i < (int)v.size () + 10; i++)  {
		f[i] = 0;
	}
	ll a =0;
	for (ll i = v.size () - 1; i >= 0; i--) {
		a += an (v[i]);
		up (v[i] + 1, 1);
	}
	return a;
}

ll count_swaps (vector<int> ve) {
	int n = ve.size ();
	vector<int> vv (n), i1[n + 1], i2[n + 1];
	vector<pair<int, pair<int ,int>>> vp;
	for (int i = 0; i < n; i++) {
		if (ve[i] < 0) {
			i1[-ve[i]].pb (i);
		}
		else {
			i2[ve[i]].pb (i);
		}
	}
	for (int i = 1; i <= n; i++) {
		while (i1[i].size ()) {
			vp.pb (mp (min (i1[i].back (), i2[i].back ()), mp (i1[i].back (), i2[i].back ())));
			i1[i].pop_back (), i2[i].pop_back ();
		}
	}
	sort (vp.begin (), vp.end ());
	for (int i = 0; i < n / 2; i++) {
		vv[vp[i].sd.ft] = 2 * i;
		vv[vp[i].sd.sd] = 2 *i + 1;
	}
	return inv (vv);
}

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