Submission #520777

#	Time	Username	Problem	Language	Result	Execution time	Memory
520777		Richw818	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	128 ms	140812 KiB

shoes

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

const int MAXN = 200005;
struct bit{
	vector<int> sum;
	bit(){
		sum.resize(MAXN);
	}
	void update(int i, int v){
		while(i < MAXN){
			sum[i] += v;
			i += i & (-i);
		}
	}
	int query(int i){
		int res = 0;
		while(i){
			res += sum[i];
			i -= i & (-i);
		}
		return res;
	}
};
int64_t count_swaps(vector<int> S){
	int n = S.size();
	n >>= 1;
	vector<deque<int>> pos(n+1), neg(n+1);
	vector<int> occ(n + 1);
	for(int i = 0; i < 2 * n; ++i){
		if(S[i] < 0)
			neg[abs(S[i])].emplace_back(i);
		else
			pos[S[i]].emplace_back(i);
		++occ[abs(S[i])];
	}
	vector<int> ord;
	for(int i = 0; i < 2 * n; ++i){
		if(S[i] < 0){
			int val = abs(S[i]);
			ord.emplace_back(neg[val][0]+1);
			ord.emplace_back(pos[val][0]+1);
			neg[val].pop_front();
			pos[val].pop_front();
		}
	}	
	bit b;
	int64_t ans = 0;
	for(auto &v : ord){
		ans += b.query(2*n) - b.query(v);
		b.update(v, 1);
	}
	return ans;
}
// int main(){
	// ios_base::sync_with_stdio(false);
	// cin.tie(nullptr);
// 	
	// return 0;
// }

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