Submission #609645

#	Time	Username	Problem	Language	Result	Execution time	Memory
609645		fvogel499	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	382 ms	40496 KiB

shoes

// #include "grader.cpp"
#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define vi vector<int>

#define size(x) (int)((x).size())

#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int p2 = 1<<18;

struct Segtree {
	Segtree() {
		t = new int [p2*2];
		for (int i = 0; i < p2*2; i++) t[i] = 0;
	}
	void upd(int x, int v) {
		for (x += p2; x; x /= 2) {
			t[x] += v;
		}
	}
	int get(int b, int e) {
		int r = 0;
		b += p2;
		e += p2;
		while (b <= e) {
			if (b%2 == 1) {
				r += t[b];
				b++;
			}
			if (e%2 == 0) {
				r += t[e];
				e--;
			}
			b /= 2;
			e /= 2;
		}
		return r;
	}
	int* t;
};

int count_swaps(vector<signed> bcc) {
	vi b;
	for (int i : bcc) b.push_back(i);
	int n = size(b);
	map<int, map<int, vi>> per;
	for (int i = n-1; i >= 0; i--) {
		int sign = 0;
		if (b[i] < 0) {
			sign = 1;
		}
		per[abs(b[i])][sign].push_back(i);
	}
	bool handled [n];
	for (int i = 0; i < n; i++) handled[i] = false;
	Segtree st = Segtree();
	int cost = 0;
	int before = 0;
	for (int i = 0; i < n; i++) if (!handled[i]) {
		int sign = 0;
		if (b[i] < 0) {
			sign = 1;
		}
		assert(size(per[abs(b[i])][sign]) == size(per[abs(b[i])][!sign]));
		assert(!per[abs(b[i])][sign].empty() && per[abs(b[i])][sign].back() == i);
		per[abs(b[i])][sign].pop_back();
		int j = per[abs(b[i])][!sign].back();
		per[abs(b[i])][!sign].pop_back();
		if (b[i] > 0) {
			cost++;
		}
		if (i+1 <= j-1) {
			int loc = st.get(i+1, j-1);
			cost += (j-1)-(i+1)+1 - loc;
		}
		st.upd(i, 1); // not needed
		st.upd(j, 1);
		handled[i] = true;
		handled[j] = true;
	}
	return cost;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:67:6: warning: unused variable 'before' [-Wunused-variable]
   67 |  int before = 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