Submission #488225

#	Time	Username	Problem	Language	Result	Execution time	Memory
488225		ssense	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	19 ms	1852 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

int get_now(vector<int> &a, vector<int> &s)
{
	vint scop = s;
	int ans = 0;
	for(int i = 0; i < s.size()/2; i++)
	{
		int idx = 0;
		while(scop[idx] != a[i])
		{
			idx++;
		}
		ans+=idx;
		scop.erase(scop.begin()+idx);
		idx = 0;
		while(scop[idx] != -a[i])
		{
			idx++;
		}
		ans+=idx;
		scop.erase(scop.begin()+idx);
	}
	return ans;
}

long long count_swaps(vector<int> s)
{
	ll n = s.size()/2;
	if(n > 1000)
	{
		return n*(n-1)/2;
	}
	else if(n <= 8)
	{
		vint a;
		for(auto x : s)
		{
			if(x < 0) a.pb(x);
		}
		int offans = get_now(a, s);
		do {
			offans = min(offans, get_now(a, s));
		} while (next_permutation(all(a)));
		return offans;
	}
	int ans = 0;
	while(s.size() > 0)
	{
		int i = 0;
		while(s[i] > 0)
		{
			i++;
		}
		ans+=i;
		int sz = -s[i];
		s.erase(s.begin()+i);
		i = 0;
		while(s[i] != sz)
		{
			i++;
		}
		ans+=i;
		s.erase(s.begin()+i);
	}
	return ans;
}
/*
int main()
{
	int n;
	cin >> n;
	vint a(2*n);
	for(int i = 0; i < 2*n; i++)
	{
		cin >> a[i];
	}
	cout << count_swaps(a);
}
 */
/*
5
-2 -1 1 2 -1 1 -2 -1 1 2
 */

Compilation message (stderr)

shoes.cpp: In function 'int get_now(std::vector<int>&, std::vector<int>&)':
shoes.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < s.size()/2; i++)
      |                 ~~^~~~~~~~~~~~

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