Submission #412383

#	Time	Username	Problem	Language	Result	Execution time	Memory
412383		bipartite_matching	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	135 ms	75968 KiB

shoes

#include <bits/stdc++.h>

#define forint(i, N) for (int i = 0; i <(N); i++)

using namespace std;

typedef long long ll;

vector<int> tree(1000000, 0);

vector< queue<pair<int, int> > > v; 

vector<int> target;

void build(int node, int a, int x, int y) {
	if (y <= a) {
		//cerr << a << " - " << x << " -- " << y << endl;
		tree[node]++;
		return;
	}
	//tree[node]++;
	//cerr << a << " ja " << x << " - "  << y << endl;
	build(node * 2 + 1, a, x, (x + y) / 2);
	if ((x + y) / 2 + 1 <= a) {
		build(node * 2 + 2, a, (x + y) / 2 + 1, y);
	}
}

ll count(int node, int a, int x, int y) {
	if (x == y) {
		//cerr << " ja " << tree[node] << endl;
		return tree[node];
	}

	if (a <= (x + y) / 2) {
		return tree[node] + count(node * 2 + 1, a, x, (x + y) / 2);
	}
	if (a >= (x + y) / 2 + 1) {
		return tree[node] + count(node * 2 + 2, a, (x + y) / 2 + 1, y);
	}
}

ll count_swaps(vector<int> s) {
	v.resize(s.size() / 2 + 1);

	target.resize(s.size(), -1);

	forint(i, s.size()) {
		if (v[abs(s[i])].empty() || v[abs(s[i])].front().first == s[i]) {
			v[abs(s[i])].push({s[i], i});
		}
		else {
			target[v[abs(s[i])].front().second] = i;
			v[abs(s[i])].pop();
		}
	}

	ll ans = 0;

	forint(i, s.size()) {
		if (target[i] == -1) {
			continue;
		}

		ans = ans + target[i] + count(0, target[i], 0, s.size() - 1) - i - count(0, i, 0, s.size() - 1);

		//cerr << "ja" << endl;

		if (s[i] < 0) {
			ans--;
		}

		//cerr << count(0, target[i], 0, s.size() - 1) << endl;

		build(0, target[i] - 1, 0, s.size() - 1);
	}

	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:3:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define forint(i, N) for (int i = 0; i <(N); i++)
      |                                        ^
shoes.cpp:48:2: note: in expansion of macro 'forint'
   48 |  forint(i, s.size()) {
      |  ^~~~~~
shoes.cpp:3:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define forint(i, N) for (int i = 0; i <(N); i++)
      |                                        ^
shoes.cpp:60:2: note: in expansion of macro 'forint'
   60 |  forint(i, s.size()) {
      |  ^~~~~~
shoes.cpp: In function 'll count(int, int, int, int)':
shoes.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

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