Submission #463989

#	Time	Username	Problem	Language	Result	Execution time	Memory
463989		wind_reaper	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	204 KiB

shoes

#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************



//***************** GLOBAL VARIABLES *****************



//***************** AUXILIARY STRUCTS *****************

struct FenwickTree{
	vector<int> tree;
	int n;
	FenwickTree(int N){
		tree.resize(N + 1);
		n = N;
	}
	void add(int x, int v){
		for(; x <= n; x += (x & (-x)))
			tree[x] += v;
	}
	int get(int x){
		int sum = 0;
		for(; x; x -= (x & (-x)))
			sum += tree[x];
		return sum;
	}
};

//***************** MAIN BODY *****************

int64_t count_swaps(vector<int> S){
	int N = S.size() / 2;
	vector<int> ord[N+1];

	for(int i = 1; i <= 2*N; i++){
		ord[abs(S[i-1])].push_back({(S[i-1] < 0 ? -i : i)});
	}

	int64_t ret = 0;

	FenwickTree X(2*N);
	// for(int i = 1; i <= 2*N; i++) X.add(i, 1);

	for(int i = 1; i <= N; i++){
		sort(ord[i].begin(), ord[i].end());
		int z = ord[i].size() >> 1;
		for(int j = z - 1; j >= 0; --j){
			int l = -ord[i][j], r = ord[i][2 * z - j - 1];
			if(l > r){
				swap(l, r);
				ret++;
			}
			// cout << i << ' ' << l << ' ' << r << ' ' << ret << '\n';
			ret += r - X.get(r) - l + X.get(l) - 1;
			X.add(r + 1, -1);
			X.add(l + 1, 1);
		}
	}

	return ret;
}

//***************** *****************

// int32_t main(){
// 	// vector<int> S = {-2, 2, 2, -2, -2, 2};
// 	vector<int> S = {2, 1, -1, -2};
// 	cout << count_swaps(S);
// }

// int32_t main(){
// 	ios_base::sync_with_stdio(NULL);
// 	cin.tie(NULL);

// 	#ifdef LOCAL
// 		auto begin = high_resolution_clock::now();
// 	#endif

// 	int tc = 1;
// 	cin >> tc; 
// 	for (int t = 0; t < tc; t++)
// 		solve();

// 	#ifdef LOCAL 
// 		auto end = high_resolution_clock::now();
// 		cout << fixed << setprecision(4);
// 		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
// 	#endif

// 	return 0;
// }

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

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