Submission #413953

#	Time	Username	Problem	Language	Result	Execution time	Memory
413953		asfd221	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	70 ms	14060 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 < 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);
	int cc = 0, c[n + 1] = {};
	ll an = 0;
	vector<int> id[n + 1];
	for (int i = 0; i < n; i++) {
		if (ve[i] < 0) {
			vv[i] = cc;
			id[-ve[i]].pb (cc);
			cc += 2;
		}
	}
	for (int i = 0; i < n; i++) {
		if (ve[i] > 0) {
			vv[i] = id[ve[i]][c[ve[i]]++] + 1;
		}
	}
	return inv (vv);
}
			

Compilation message (stderr)

shoes.cpp: In function 'll inv(std::vector<int>)':
shoes.cpp:75:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (ll i = 0; i < v.size () + 10; i++)  {
      |                 ~~^~~~~~~~~~~~~~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:90:5: warning: unused variable 'an' [-Wunused-variable]
   90 |  ll an = 0;
      |     ^~

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