Submission #488353

#	Time	Username	Problem	Language	Result	Execution time	Memory
488353		ssense	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	153 ms	140172 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl

queue<int> q[200005];

struct FenwickTree {
	vector<ll> bit;  // binary indexed tree
	int n;
	
	FenwickTree(int n) {
		this->n = n;
		bit.assign(n, 0);
	}
	
	FenwickTree(vector<int> a) : FenwickTree(a.size()) {
		for (size_t i = 0; i < a.size(); i++)
		add(i, a[i]);
	}
	
	ll sum(int r) {
		ll ret = 0;
		for (; r >= 0; r = (r & (r + 1)) - 1)
		ret += bit[r];
		return ret;
	}
	
	ll sum(int l, int r) {
		ll ret = sum(r);
		if(l)ret -= sum(l - 1);
		return ret;
	}
	
	void add(int idx, int delta) {
		for (; idx < n; idx = idx | (idx + 1))
		bit[idx] += delta;
	}
};


long long count_swaps(vector<int> s)
{
	int n = s.size();
	for(int i = 0; i < n; i++)
	{
		q[s[i]+n/2].push(i);
	}
	vector<bool> st(n+5);
	int cnt = 1;
	for(int i = 0; i < n; i++)
	{
		if(!st[i])
		{
			if(s[i] > 0)
			{
				int p = s[i];
				s[i] = cnt+1;
				st[i] = true;
				s[q[n/2-p].front()] = cnt;
				st[q[n/2-p].front()] = true;
				q[p+n/2].pop();
				q[n/2-p].pop();
				cnt+=2;
			}
			else
			{
				int p = abs(s[i]);
				s[i] = cnt;
				st[i] = true;
				s[q[p+n/2].front()] = cnt+1;
				st[q[p+n/2].front()] = true;
				q[n/2-p].pop();
				q[p+n/2].pop();
				cnt+=2;
			}
		}
	}
	ll ans = 0;
	FenwickTree ft(n+15);
	for(int i = 0; i < n; i++)
	{
		ans+=ft.sum(s[i]+1, n+10);
		ft.add(s[i], 1);
	}
	return ans;
}
/*
int main()
{
	int n;
	cin >> n;
	vint a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << count_swaps(a) << endl;
}
 */
/*
int main()
{
	int bound = 2;
	vint now;
	for(int i = -bound; i <= bound; i++)
	{
		if(i != 0)
		{
			now.pb(i);
		}
	}
	do {
		if(count_swaps1(now) != count_swaps2(now))
		{
			cout << count_swaps1(now) << endl;
			cout << count_swaps2(now) << endl;
			for(auto x : now)
			{
				cout << x << " ";
			}
			cout << endl;
			return 0;
		}
	} while (next_permutation(all(now)));
}
*/
/*
4
1 -2 -1 2
 */

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