Submission #896615

#	Time	Username	Problem	Language	Result	Execution time	Memory
896615		aqxa	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	92 ms	29128 KiB

shoes

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

using ll = long long; 

struct segtree {
	int n; vector<int> t; 
	segtree(int _n) : n(_n) {
		t = vector<int>(2 * n, 0); 
	}
	void set(int x) {
		t[x + n] = x; 
	}
	void add(int l, int r, int x) {
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l&1) t[l++] += x;
			if (r&1) t[--r] += x;
		}
	}
	int get(int p) {
		int res = 0; 
		for (p += n; p > 0; p /= 2) res += t[p]; 
		return res; 
	}
}; 
 
int64_t count_swaps(vector<int> a) {
	int n = a.size(); 
	vector<vector<vector<int>>> pos(n + 1, vector<vector<int>>(2)); 
	for (int i = 0; i < n; ++i) {
		pos[abs(a[i])][a[i] > 0].push_back(i); 
	}
	vector<pair<int, int>> ps; 
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < pos[i][0].size(); ++j) {
			ps.push_back({pos[i][0][j], pos[i][1][j]}); 
		}
	}
	sort(ps.begin(), ps.end()); 
	segtree st(n);
	for (int i = 0; i < n / 2; ++i) {
		st.set(ps[i].first); 
		st.set(ps[i].second); 
	}

	ll ans = 0; 

	for (int i = 0; i < n / 2; ++i) {
		int tl = 2 * i, tr = 2 * i + 1; 
		int cl = st.get(ps[i].first);
		if (tl > cl) {
			assert(false);
			// cout << "g1\n"; 
			// return -1; 
		}
		ans += cl - tl; 
		// cout << "! " << cl << ' ' << tl << '\n';
		st.add(0, ps[i].first + 1, 1); 
		// for (int j = 0; j < n; ++j) {
		// 	cout << st.get(j) << " \n"[j + 1 == n]; 
		// }
		int cr = st.get(ps[i].second); 
		if (tr > cr) {	
			assert(false); 
			// cout << "g2\n"; 
			// cout << tr << ' ' << cr << '\n';
			// return -1; 
		}
		ans += cr - tr; 
		// cout << "! " << cr << ' ' << tr << '\n';
		st.add(0, ps[i].second + 1, 1); 
		// for (int j = 0; j < n; ++j) {
		// 	cout << st.get(j) << " \n"[j + 1 == n]; 
		// }
		// cout << "after " << i + 1 << " times: " << ans << "\n";
	}

	return ans; 
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int tt; 
// 	cin >> tt; 
// 	for (int t = 1; t <= tt; ++t) {
// 		int n; 
// 		cin >> n; 
// 		vector<int> a(n); 
// 		for (auto & x: a) cin >> x; 
// 		cout << "---- Start test case " << t << " ---- \n"; 
// 		for (auto & x: a) cout << x << " ";
// 		cout << "is array\n";
// 		cout << count_swaps(a) << "\n";
// 	}
	
// 	return 0; 
// }

Compilation message (stderr)

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

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