Submission #1010920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010920		alex_2008	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	16 ms	4956 KiB

shoes

//#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 110;
bool used[N];
int fenwick[N];
void update(int ind, int diff, int n) {
	while (ind <= n) {
		fenwick[ind] += diff;
		ind += (ind & (-ind));
	}
}
int sm(int ind) {
	int ans = 0;
	while (ind > 0) {
		ans += fenwick[ind];
		ind -= (ind & (-ind));
	}
	return ans;
}
ll count_swaps(vector<int> S) {
	int n = (int)S.size() / 2;
	if (n <= 1000) {
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			int ind1 = -1, ind2 = -1;
			for (int j = 2 * i; j < 2 * n; j++) {
				if (S[j] < 0) {
					ind1 = j;
					break;
				}
			}
			int x = S[ind1];
			for (int j = ind1; j > 2 * i; j--) {
				ans++;
				swap(S[j], S[j - 1]);
			}
			for (int j = 2 * i + 1; j < 2 * n; j++) {
				if (S[j] == -x) {
					ind2 = j;
					break;
				}
			}
			for (int j = ind2; j > 2 * i + 1; j--) {
				ans++;
				swap(S[j], S[j - 1]);
			}
		}
		return ans;
	}
	bool ch = true;
	for (auto& it : S) {
		if (abs(it) != abs(S[0])) ch = false;
	}
	if (ch) {
		//cout << "?\n";
		vector <int> a;
		vector <int> b;
		for (int i = 0; i < 2 * n; i++) {
			if (S[i] < 0) a.push_back(i + 1);
			else b.push_back(i + 1);
			update(i + 1, 1, 2 * n);
		}
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			ans += sm(a[i] - 1); update(a[i], -1, 2 * n);
			ans += sm(b[i] - 1); update(b[i], -1, 2 * n);
		}
		return ans;
	}
}
/*
int main() {
	cout << count_swaps({ -2, 2, 2, -2, -2, 2 }) << "\n";
}
*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

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