Submission #339031

#TimeUsernameProblemLanguageResultExecution timeMemory
339031yoavLArranging Shoes (IOI19_shoes)C++14
50 / 100
1087 ms4716 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long
#define vll vector<ll>

using namespace std;

ll count_swaps(vector<int> S)
{
	ll n = S.size()/2;
	vll arr(2 * n);
	for (ll i = 0; i < 2 * n; i++) arr[i] = S[i];
	
	/*
	cout << "arr: " << endl;
	for (ll i = 0; i < 2 * n; i++)
	{
		cout << arr[i] << " ";
	}
	*/
	ll ans = 0;
	for (ll i = 0; i < 2 * n; i += 2)
	{
		ll ind = -1;
		for (ll j = i + 1; j < 2*n; j++)
		{
			if (arr[j] == -arr[i])
			{
				ind = j;
				break;
			}
		}
		//cout << "ind: " << ind << endl;
		for (ll j = ind; j > i+1; j--)
		{
			swap(arr[j], arr[j - 1]);
			ans++;
		}
		if (arr[i+1] < arr[i])
		{
			swap(arr[i], arr[i + 1]);
			ans++;
		}
	}
	/*
	cout << "arr: " << endl;
	for (ll i = 0; i < 2 * n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	*/
	//cout << ans << endl;
	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

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...