Submission #1239283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239283		arvxs	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	1094 ms	320 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

struct BIT {
        int n;
        vector<int> t;
        BIT(int _n):n(_n),t(n+1,0){}
        void add(int i,int v){ for(;i<=n;i+=i&-i) t[i]+=v; }
        int sum(int i){ int r=0; for(;i>0;i-=i&-i) r+=t[i]; return r;}
};

long long count_swaps(vector<int> S) {

	// vector of occurences for each type
	int N = S.size();
	vector<pair<int, int> > occ[N / 2 + 1];

	for (int i = 0; i < N; i++) {
		occ[abs(S[i])].push_back({S[i], i});
	}

	long long ans = 0;

	vector<pair<int, int> > intervals;

	for (int x = 1; x <= N / 2; x++) {
		vector<pair<int, int> > &v = occ[x];

		int m = v.size() / 2;
		sort(v.begin(), v.end());

		for (int i = 0; i < m; i++) {
			int l = v[i].second;
			int r = v[i + m].second;

			if (l > r) {
				swap(l, r);
				ans++;
			}

			intervals.push_back({l + 1, r + 1});
		}
	}

	sort(intervals.begin(), intervals.end());

	BIT bit(N);
	for (int i = 1; i <= N; i++) 
		bit.add(i, 1);	

	for (int i = 1; i <= N; i++) {
		int l = intervals[i].first;
		int r = intervals[i].second;
		bit.add(i, 1);
		ans += bit.sum(r - 1) - bit.sum(l);
		bit.add(l, -1);
        bit.add(r, -1);
	}


	return ans;

}

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