Submission #964457

#	Time	Username	Problem	Language	Result	Execution time	Memory
964457		beaboss	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	222 ms	274196 KiB

shoes

// Source: https://oj.uz/problem/view/IOI19_shoes
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 2e5 + 10;

struct BIT {
private:
	int sz;
	vi bit;

public:
	BIT(int n) : sz(n), bit(n + 1) {}

	void add(int pos, int val) {
		pos++;
		for (; pos <= sz; pos += (pos & -pos)) {
			bit[pos] += val;
		}
	}

	int pref(int ind) {
		ind++;
		int res = 0;
		for (; ind > 0; ind -= (ind & -ind)) res += bit[ind];
		return res; 
	}
};

queue<int> l[N], r[N];

BIT bit(N);

ll count_swaps(vi s) {
	int n = s.size();
	FOR(i, 0, n) {
		if (s[i] < 0) l[-s[i]].push(i);
		else r[s[i]].push(i);
		bit.add(i, 1);
	}
	ll ans = 0;
	FOR(i, 0, n) {
		if (s[i] != 0) {
			int nxt;
			if (s[i] > 0) {
				nxt = l[s[i]].front();
				ans++;
			} else {
				nxt = r[-s[i]].front();
				s[i] = -s[i];
			}
			r[s[i]].pop();
			l[s[i]].pop();

			bit.add(i, -1);
			s[i] = 0;
			s[nxt] = 0;
			bit.add(nxt, -1);
			ans += bit.pref(nxt);


		}
	}

	return ans;

}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	cout << count_swaps({2, 1, -1, -2}) << endl;
// }

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