Submission #622456

#	Time	Username	Problem	Language	Result	Execution time	Memory
622456		Jomnoi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	160 ms	139644 KiB

shoes

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

const int MAX_N = 2e5 + 5;

int N;
long long ans;
queue <int> pos[MAX_N];
bool visited[MAX_N];
int tree[MAX_N];

void add(int x, int v) {
	for(int i = x; i < MAX_N; i += (i & -i)) {
		tree[i] += v;
	}
}

int get(int x) {
	int res = 0;
	for(int i = x; i >= 1; i -= (i & -i)) {
		res += tree[i];
	}
	return res;
}

long long count_swaps(vector <int> s) {
	for(int i = 1; i < MAX_N; i++) {
		tree[i] = i & -i;
	}

	N = s.size();
	s.insert(s.begin(), 0);
	
	for(int i = 1; i <= N; i++) {
		if(s[i] < 0) {
			s[i] = N + s[i] + 1;
		}

		pos[s[i]].push(i);
	}

	for(int i = 1; i <= N; i++) {
		if(visited[i] == true) {
			continue;
		}

		int now = s[i], nxt = N - s[i] + 1, nxtpos;
		if(s[i] > N / 2) {
			ans--;
		}

		nxtpos = pos[nxt].front();
		pos[nxt].pop();
		pos[now].pop();

		ans += get(nxtpos) - get(i);
		add(nxtpos, -1);
		visited[i] = visited[nxtpos] = true;
	}
	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