Submission #701140

#	Time	Username	Problem	Language	Result	Execution time	Memory
701140		mychecksedad	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	189 ms	140180 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e6;

int t[N], n;
void add(int v){
	while(v > 0){
		t[v]++;
		v -= (v&-v);
	}
}
int get(int v){
	int res=0;
	while(v <= n*2){
		res+=t[v];
		v+=(v&-v);
	}
	return res;
}

long long count_swaps(vector<int> s) {
	long long ans = 0, c = 0;
	
	n = s.size()/2;

	deque<int> pos[n + 1][2];
	vector<int> A (s.size());

	for(int i = 0; i <= 2*n; ++i) t[i] = 0;

	for(int i = 0; i < 2*n; ++i){
		if(s[i] < 0)
			pos[-s[i]][0].pb(i);
		else
			pos[s[i]][1].pb(i);
	}
	vector<bool> vis(2*n);
	for(int i = 0; i < 2*n; ++i){
		if(vis[i]) continue;
		if(s[i] < 0){
			int val = pos[-s[i]][1].front();
			int go = pos[-s[i]][1].front() + get(pos[-s[i]][1].front() + 1);
			vis[val] = 1;
			pos[-s[i]][1].pop_front();
			pos[-s[i]][0].pop_front();
			int pos = i + get(i + 1);
			ans += abs(go-pos-1);
			add(val + 1);
		}else{
			int val = pos[s[i]][0].front();
			int go = pos[s[i]][0].front() + get(pos[s[i]][0].front() + 1);
			vis[val] = 1;
			pos[s[i]][0].pop_front();
			pos[s[i]][1].pop_front();
			int pos = i + get(i + 1);
			ans += abs(pos-go);
			add(val + 1);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:24:21: warning: unused variable 'c' [-Wunused-variable]
   24 |  long long ans = 0, c = 0;
      |                     ^

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