Submission #896621

#	Time	Username	Problem	Language	Result	Execution time	Memory
896621		aqxa	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	100 ms	29176 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 slow(vector<int> a) {
	int n = a.size(); 
	vector<int> p; 
	for (int i = 0; i < n; ++i) p.push_back(i); 
	ll ans = 1e9; 
	do {
		int ok = 1; 
		for (int i = 0; i < n; i += 2) {
			ok &= (abs(a[p[i]]) == a[p[i + 1]]); 
		}
		if (ok) {
			int cnt = 0; 
			for (int i = 0; i < n; ++i) {
				for (int j = i + 1; j < n; ++j) {
					cnt += p[i] > p[j]; 
				}
			}
			ans = min(ans,(ll) cnt); 
		}
	} while (next_permutation(p.begin(), p.end())); 
	return ans; 
}
 
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(), [](pair<int, int> & x, pair<int, int> & y){
		// return x.first < y.first; 
		return min(x.first, x.second) < min(y.first, y.second); 
	}); 
	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; 
}


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rng0(ll B) {
	return (unsigned long long)rng() % B;
}

vector<int> gen(int n) {
	vector<int> ret; 
	for (int i = 0; i < n; ++i) {
		ret.push_back(rng0(n) + 1); 
		ret.push_back(ret.back() * -1); 
	}
	random_shuffle(ret.begin(), ret.end()); 
	return ret; 
}
\
// 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 = gen(4); 
// 		// for (auto & x: a) cin >> x; 
// 		// cout << "---- Start test case " << t << " ---- \n"; 
// 		// for (auto & x: a) cout << x << " ";
// 		// cout << "is array\n";
// 		ll ans = count_swaps(a); 
// 		ll ans2 = slow(a); 
// 		if (ans != ans2) {
// 			cout << "!!!!!!!!!!!!!!!!\n";
// 			for (auto & x: a) cout << x << " ";
// 			cout << "is array\n";
// 			cout << ans << ' ' << ans2 << '\n';
// 			exit(0); 
// 		}
// 		// cout << count_swaps(a) << "\n";
// 	}
	
// 	return 0; 
// }

Compilation message (stderr)

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

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