제출 #339055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339055		yoavL	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	364 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define vb vector<bool>

using namespace std;

vll arr, seg;
ll n;


void make_seg()
{
	ll len = 1;
	while (len < 4 * n) len <<= 1;

	seg.resize(len);
	for (ll i = 0; i < 2*n; i++)
	{
		//seg[len / 2 + i] = arr[i];
		seg[len / 2 + i] = 0;
	}
	for (ll i = len / 2-1; i > 0; i--)
	{
		seg[i] = seg[2 * i] + seg[2 * i + 1];
	}
}


void up(ll ind, ll add)
{
	ll len = seg.size();
	ind += len / 2;
	seg[ind] += add;
	ind >>= 1;
	while (ind)
	{
		seg[ind] = seg[2 * ind] + seg[2 * ind + 1];
		ind >>= 1;
	}
}

ll q(ll a, ll b)
{
	ll len = seg.size();
	a += len / 2, b += len / 2;
	ll ans = 0;
	while (a <= b)
	{
		if (a % 2 == 1) ans += seg[a++];
		if (b % 2 == 0) ans += seg[b--];
		a >>= 1, b >>= 1;
	}
	return ans;
}

ll count_swaps(vector<int> S)
{
	n = S.size()/2;
	arr.resize(2 * n);
	
	for (ll i = 0; i < 2 * n; i++)
	{
		arr[i] = S[i];

	}
	vector<queue<ll>> plus(n+1);
	vector<queue<ll>> minus(n+1);

	for (ll i = 0; i < 2 * n; i++)
	{
		if (arr[i] > 0)
		{
			plus[abs(arr[i])].push(i);
		}
		else
		{
			minus[abs(arr[i])].push(i);
		}
	}
	/*
	cout << "plus: " << endl;
	for (ll i = 0; i < n + 1; i++)
	{
		while (!plus[i].empty())
		{
			cout << plus[i].front() << " ";
			plus[i].pop();
		}
		cout << endl;
	}
	cout << endl;
	cout << "minus: " << endl;
	for (ll i = 0; i < n + 1; i++)
	{
		while (!minus[i].empty())
		{
			cout << minus[i].front() << " ";
			minus[i].pop();
		}
		cout << endl;
	}
	cout << endl;
	for (ll i = 0; i < 2 * n; i++)
	{
		if (arr[i] > 0)
		{
			plus[abs(arr[i])].push(i);
		}
		else
		{
			minus[abs(arr[i])].push(i);
		}
	}
	*/
	ll ans = 0;
	make_seg();
	vb did(2 * n, 0);
	for (ll i = 0; i < 2*n; i++)
	{
		if (did[i]) continue;
		//cout << "val: " << arr[i] << endl;
		ll nextind;
		//ll realfind = i + q(i + 1, 2 * n - 1);
		if (arr[i] > 0)
		{
			plus[abs(arr[i])].pop();
			nextind = minus[abs(arr[i])].front();
			minus[abs(arr[i])].pop();
		}
		else
		{
			minus[abs(arr[i])].pop();
			nextind = plus[abs(arr[i])].front();
			plus[abs(arr[i])].pop();
		}
		//cout << "nextind: " << nextind << endl;
		did[nextind] = true;
		ll realind = nextind + q(nextind + 1, 2 * n - 1);
		//cout << "realind: " << realind << endl;
		ll realfind = i + q(i + 1, 2 * n - 1);
		//cout << "realfind: " << realfind << endl;
		//ll cost = max(abs(realind - realfind)-1, (ll)0);
		//if (arr[i] > 0 && realind > realfind) cost++;
		//else if (arr[i] < 0 && realind < realfind) cost++;
		ll cost = max(realind - realfind - 1, (ll)0);
		if (arr[i] > 0) cost++;
		ans += cost;
		up(realfind, 1);
	}
	return ans;
}

/*
int main()
{
	ll n;
	cin >> n;
	vector<int> arr(2 * n);
	for (ll i = 0; i < 2 * n; i++) cin >> arr[i];
	ll ans = count_swaps(arr);

	cout << "ans: " << ans << endl;
}
*/


/*

2
2 1 -1 -2

14:56

3
1 -1 -1 1 1 -1


*/

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