Submission #160116

#	Time	Username	Problem	Language	Result	Execution time	Memory
160116		mth1908	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	3 ms	376 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

struct FenwickTree {
	vector<int> a;
	int n;

	FenwickTree(int n){
		this -> n = n;
		a.assign(n, 0);
	}

	int count(int j){
		int cnt = 0;
		for(; j >= 0; j = (j & (j + 1)) - 1) cnt += a[j];
		return cnt;
	}

	int count(int l, int r){
		return (count(r) - count(l - 1));
	}

	void put(int id){
		for(; id < n; id = id | (id + 1)) a[id]++;
	}
};

vector<int> create_ind(int n, vector<int> &s){
	vector<int> ind(2 * n + 1);
	for(int i = 0; i < 2 * n + 1; i++) ind[s[i] + n] = i;
	return ind;
}

long long count_adj(int n, vector<int> &s){
	vector<int> id = create_ind(n, s);
	FenwickTree ft = FenwickTree(2 * n);
	long long ans = 0;
	for(int i = 0; i < 2 * n; i++){
		if(s[i] != 0){
			int pos = id[-s[i] + n];
			ans += pos - i - ft.count(i, pos) - (s[i] < 0 ? 1 : 0);
			s[pos] = 0;
			ft.put(pos);
		}
	}
	return ans;
}

vector<int> change(vector<int> v){
	int n = (int) v.size() / 2;
	vector<int> cnt(n, 0);

	for(int i = 0; i < 2 * n; i++) 
		if(v[i] > 0) cnt[v[i] - 1]++;
	for(int i = 1; i < n; i++) cnt[i] += cnt[i - 1];

	vector<int> cntl = cnt, cntr = cnt;

	for(int i = 0; i < 2 * n; i++){
		if(v[i] > 0) v[i] = (--cntr[v[i] - 1]) + 1;
		else v[i] = -((--cntr[v[i] - 1]) + 1);
	}

	return v;
}

long long count_swaps(vector<int> s){
	s = change(s);
	int n = s.size() / 2;
	return count_adj(n, s);
}

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