Submission #152057

#	Time	Username	Problem	Language	Result	Execution time	Memory
152057		oolimry	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	34 ms	3804 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
 
long long tree[200005];
long long N;
void update(int x){
	x += N;
	while(x > 0){
		tree[x]++;
		x >>= 1;
	}
}
 
long long query(int l, int r){
	long long ans = 0;
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans += tree[l];
			l++;
		}
		if(r&1){
			r--;
			ans += tree[r];
		}
	}
	return ans;
}
long long count_swaps(std::vector<int> s) {
	long long n = s.size() / 2;
	N = 2 * n;
	long long ans = 0;
	
	for(int i = 0;i < 2 * n;i++){
		if(s[i] < 0) s[i] = (s[i] * -1) - 1;
		else s[i] = s[i] - 1 + n;
		
		//stuff[s[i]].push_back(i);
	}
	
	int pos = 0;
	for(int i = 0;i < 2 * n;i++){
		
		if(query(i,i+1) != 0) continue;
		int x = s[i];
		int y = 0;
		if(x < n) y = x + n;
		else y = x - n;
		
		int l = i;
		int r = l;
		for(int j = l;j < 2*n;j++){
			if(s[j] == y){
				r = j;
				break;
			}
		}
		
		
		int nl = l + query(l+1,2*n); 
		int nr = r + query(r+1,2*n); 
		//cout << i << " " << l << " " << r << " " << nl << " " << nr << " " << ans << "\n";
		if(x < n){
			ans += (nl - 2 * pos);
			ans += (nr - (2 * pos + 1));
		}
		else{
			ans += (nr - 2 * pos);
			ans += (nl - (2 * pos + 1));
			ans++;
		}
		
		pos++;
		
		update(l);
		update(r);
		s[l] = -1;
		s[r] = -1;
	}
	
	
 
	return ans;
}

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