Submission #152051

#	Time	Username	Problem	Language	Result	Execution time	Memory
152051		oolimry	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	3 ms	504 KiB

shoes

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

static int tree[300005];
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;
	
	int nxt[2*n];
	
	int stuff[2*n];
	fill(stuff,stuff+2*n,-1);
	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;
		
	}
	
	for(int i = 0;i < 2 * n;i++){
		int x = s[i];
		int y = 0;
		if(x < n) y = x + n;
		else y = x - n;
		if(stuff[y] == -1){
			stuff[x] = i;
		}
		else{
			nxt[stuff[y]] = i;
			nxt[i] = -1;
			stuff[y] = -1;
		}
	}
	//for(int i = 0;i < 2 * n;i++) cout << nxt[i] << " ";
	int pos = 0;
	
	for(int i = 0;i < 2 * n;i++){
		
		if(query(i,i+1) != 0) continue;
		if(nxt[i] == -1) continue;
		int x = s[i];
		int y = 0;
		if(x < n) y = x + n;
		else y = x - n;
		
		int l = i;
		//if(stuff[y].empty()) while(true) continue;
		int r = nxt[i]; 
		//int r = stuff[y].front();
		//stuff[y].pop();
		//if(stuff[x].empty()) while(true) continue;
		//stuff[x].pop();
		
		
		
		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);
	}
	
	

	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:65:7: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   int y = 0;
       ^

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