Submission #210811

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

shoes

#include<iostream>
#include<cmath>

#include "shoes.h"
using namespace std;

#define int long long

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)
	{
		int sum = 0;
		for (int i=a;i<=b;i++)
			sum += v[i];
		return sum;
	}
	
	inline void upd(int n, int vv)
	{
		v[n]+=vv;
	}
	
	FT(int cN): N(cN+5), v(N) {  }
};

#undef int
long long count_swaps(std::vector<int> v)
#define int long long
{
	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;
}
#undef int

#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

Compilation message (stderr)

shoes.cpp: In member function 'long long int FT::query(long long int)':
shoes.cpp:22:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^

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