Submission #413978

#	Time	Username	Problem	Language	Result	Execution time	Memory
413978		asfd221	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	332 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 = 2e5 + 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), v2 (n);
	int cc = 0, c[n + 1] = {}, c2 = 1, d[n + 1] = {};
	vector<int> id[n + 1], i2[n + 1];
	for (int i = 0; i < n; i++) {
		if (ve[i] < 0) {
			vv[i] = cc;
			id[-ve[i]].pb (cc);
			cc += 2;
		}
		else {
			v2[i] = c2;
			i2[ve[i]].pb (c2);
			c2 += 2;
		}
	}
	for (int i = 0; i < n; i++) {
		if (ve[i] > 0) {
			vv[i] = id[ve[i]][c[ve[i]]++] + 1;
		}
		else {
			vv[i] = i2[-ve[i]][d[-ve[i]]++] - 1;
		}
	}
	return min (inv (vv), inv (v2));
}
			

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