Submission #285126

#	Time	Username	Problem	Language	Result	Execution time	Memory
285126		cookiedoth	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	227 ms	15732 KiB

shoes

/*

Code for problem A by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


______▄███████▄_______
______█▄█████▄█_______
______█▼▼▼▼▼█_______
_____██________ ██______
______█▲▲▲▲▲█_______
______█████████_______
_______██____ ██________

=_=
¯\_(ツ)_/¯
o_O

*/

#include "shoes.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct fenwick {
	vector<int> t;
	int n;
	
	void init(int _n) {
		n = _n;
		t.resize(n);
	}

	void add(int pos, int val) {
		while (pos < n) {
			t[pos] += val;
			pos = (pos | (pos + 1));
		}
	}

	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += t[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

int n;

ll count_swaps(vector<int> s) {
	map<int, vector<int> > positive;
	n = s.size();
	for (int i = n - 1; i >= 0; --i) {
		if (s[i] > 0) {
			positive[s[i]].push_back(i);
		}
	}
	vector<int> to(n);
	int ptr = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] < 0) {
			to[i] = ptr++;
			to[positive[-s[i]].back()] = ptr++;
			positive[-s[i]].pop_back();
		}
	}
	ll ans = 0;
	fenwick f;
	f.init(n);
	for (int i = 0; i < n; ++i) {
		ans += f.get(to[i] + 1, n - 1);
		f.add(to[i], 1);
	}
	return ans;
}

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