Submission #157554

#	Time	Username	Problem	Language	Result	Execution time	Memory
157554		ioane	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	399 ms	26808 KiB

shoes

#include "shoes.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define LL long long
#define PB push_back

using namespace __gnu_pbds;
using namespace std;  

long long count_swaps(std::vector<int> s) {
	LL n = s.size()/2;
	ordered_set ss;
	vector < LL > v[n*2+1];
	LL a[n*2+1], fix[n*2+1];
	LL ans = 0;
	for ( LL i = 0; i < 2*n; ++i ){
		if ( s[i] < 0 ){
			s[i] = n - s[i];
		}
		ss.insert(i);
		v[s[i]].PB(i);
		a[i+1]=0;
		fix[i] = 0;
	}/**/
	for ( LL i = 0; i < 2*n; ++i ){
		if ( fix[i] ) continue;
		ss.erase(i);
		LL k = s[i];
		a[k]++;
		if ( k > n ) k -= n;
		else k += n;
		//cout << i << " " << k << " " << a[k] << endl;
		//while ( v[k][a[k]] <= i ) a[k]++;
		LL t = v[k][a[k]];
		a[k]++;
		ans += ss.order_of_key(t);
		if ( k > n ) ans++;
		fix[t] = 1;
		ss.erase(t);
	}/**/

	return ans;
}

/*/
int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
	assert(1 == scanf("%d", &S[i]));
	fclose(stdin);
	
	long long result = count_swaps(S);
	
	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
/**/

Compilation message (stderr)

shoes.cpp:62:1: warning: "/*" within comment [-Wcomment]
 /**/

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