Submission #210796

#	Time	Username	Problem	Language	Result	Execution time	Memory
210796		dOAOb	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	6 ms	376 KiB

shoes

#include<iostream>
#include<cmath>

#include "shoes.h"
using namespace std;

//#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

typedef pair<int, int> pii;

struct FT
{
	int N;
	vector<int> v;
	
	inline int query(int n)
	{
		int sum = 0;
		for (n+=2; n; n-=n&-n)
			sum += v[n];
		return sum;
	}
	
	inline int ask(int a, int b)
	{
		return query(b) - query(a-1);
	}
	
	inline void upd(int n, int vv)
	{
		for (n+=2; n<N; n+=n&-n)
			v[n] += vv;
	}
	
	FT(int cN): N(cN+5), v(N) {  }
};

long long count_swaps(std::vector<int> v)
{
	int n = v.size();
	vector<vector<pii>> sh(n+1);
	for (int i=0;i<n;i++)
		sh[abs(v[i])].push_back({i, v[i]>0});
	
	int sum = 0;
	FT ft(n);
	for (int i=1;i<=n;i++)
	{
		vector<pii> &shi = sh[i];
		int m = shi.size();
		for (int sr=0, j=0;j<m;j++)
		{
			if (!shi[j].second) sum += sr, sr--;
			else sr++;
		}
		
		for (int j=1;j<m;j+=2)
		{
			sum += ft.ask(shi[j-1].first, shi[j].first);
		}
		
		for (int j=0;j<m;j++)
			ft.upd(shi[j].first, 1);
	}
	
	return sum;
}

#ifdef lioraju
	signed main()
	{
		int n; cin>>n, n*=2;
		vector<int> v(n);
		for (int &x: v)
			cin>>x;
		
		cout<<count_swaps(v)<<'\n';
	}
#endif

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