Submission #285139

#	Time	Username	Problem	Language	Result	Execution time	Memory
285139		cookiedoth	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	279 ms	27512 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);
	}
};

map<int, vector<int> > L, R;
vector<int> flip, used;
int n;
ll ans;

void add_pair(int i, int j) {
	if (i > j) {
		ans++;
	}
	flip[i] = j;
	flip[j] = i;
}

ll count_swaps(vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; ++i) {
		if (s[i] < 0) {
			L[s[i]].push_back(i);
		} else {
			R[-s[i]].push_back(i);
		}
	}
	flip.resize(n);
	for (auto pp : L) {
		vector<int> vL = pp.second, vR = R[pp.first];
		for (int i = 0; i < vL.size(); ++i) {
			add_pair(vL[i], vR[i]);
		}
	}
	used.resize(n);
	fenwick f;
	f.init(n);
	for (int i = 0; i < n; ++i) {
		f.add(i, 1);
	}
	for (int i = 0; i < n; ++i) {
		if (used[i] == 0) {
			ans += f.get(i + 1, flip[i] - 1);
			used[i] = 1;
			used[flip[i]] = 1;
			f.add(i, -1);
			f.add(flip[i], -1);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for (int i = 0; i < vL.size(); ++i) {
      |                   ~~^~~~~~~~~~~

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