Submission #596150

#	Time	Username	Problem	Language	Result	Execution time	Memory
596150		alireza_kaviani	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	83 ms	14500 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define SZ(x)			int((x).size())
#define all(x)			(x).begin() , (x).end()
#define sep				' '

const int MAXN = 2e5 + 10;

int n , mark[MAXN] , fen[MAXN];
vector<int> ind[MAXN];

void add(int x , int val){
	for(x++ ; x < MAXN ; x += x & -x)	fen[x] += val;
}

int get(int x){
	int ans = 0;
	for( ; x ; x -= x & -x)	ans += fen[x];
	return ans;
}

ll count_swaps(vector<int> s) {
	n = SZ(s) / 2;
	for(int i = 2 * n - 1 ; i >= 0 ; i--){
		ind[s[i] + n].push_back(i);
		add(i , 1);
	}
	ll ans = 0;
	for(int i = 0 ; i < 2 * n ; i++){
		if(mark[i])	continue;
		ind[s[i] + n].pop_back();
		int nxt = ind[-s[i] + n].back();
		ind[-s[i] + n].pop_back();
		add(i , -1);
		ans += get(nxt);
		add(nxt , -1);
		mark[i] = mark[nxt] = 1;
		if(s[i] > s[nxt])	ans++;
	}
	return ans;
}

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