Submission #772697

#	Time	Username	Problem	Language	Result	Execution time	Memory
772697		Abrar_Al_Samit	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	265 ms	22708 KiB

shoes

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


const int nax = 2e5 + 3;
struct bit {
	int a[nax] = {0};

	void add(int i) {
		while(i<nax) {
			++a[i];
			i += i&-i;
		}
	}
	int query(int i) {
		int ret = 0;
		while(i>0) {
			ret += a[i];
			i -= i&-i;
		}
		return ret;
	}

	int query(int l, int r) {
		if(l==0) return query(r);
		return query(r) - query(l-1);
	}
} b;
long long count_swaps(vector<int> s) {
	int n = s.size();

	set<pair<int,int>>by_index, by_color;

	for(int i=0; i<n; ++i) {
		by_index.insert(make_pair(i, s[i]));
		by_color.insert(make_pair(s[i], i));
	}

	long long ans = 0;

	int cur_index = 0;
	while(!by_index.empty()) {
		auto x = *by_index.begin();
		by_index.erase(x);

		by_color.erase(make_pair(x.second, x.first));

		auto y = *by_color.lower_bound(make_pair(-x.second, -1));
		by_color.erase(y);
		by_index.erase(make_pair(y.second, y.first));

		if(x.second>0) ++ans;

		//find real index of y.second
		int inc = b.query(y.second, n);
		int real_index = y.second + inc;
		ans += real_index - cur_index - 1;

		b.add(y.second);


		cur_index += 2;
	}
	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