Submission #288890

#	Time	Username	Problem	Language	Result	Execution time	Memory
288890		mohammad	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	96 ms	17620 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
 
#define endl "\n"
// #define int long long

typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;
const int N = 400010  ;

int n ;

struct BIT {
	int bit[400010];

	ll sum(ll i) {
		ll ret = 0;
		for (++i; i > 0; i -= i & -i)
			ret += bit[i];
		return ret;
	}

	void add(ll i, ll v) {
		for (++i; i < N; i += i & -i) bit[i] += v;
	}

}tree;

vector<pair<int , int>> v[N] , g; 

ll count_swaps(vector<int> s) {
	n = s.size() / 2;
	for(int i = 0 ; i < n * 2 ; ++i)
		v[abs(s[i])].push_back({s[i] , i});
	ll ans = 0 ;
	for(int i = 1 ; i <= n ; ++i){
		sort(v[i].begin(), v[i].end());
		int sz = v[i].size() / 2;
		for(int j = 0 ; j < sz ; ++j){
			int l = v[i][j].second + 1;
			int r = v[i][j + sz].second + 1;
			if(l > r) ans++ , swap(l , r);
			g.push_back({l , r});
		}
	}
	sort(g.begin(), g.end());	
	for(int i = 1; i <= 2 * n ; ++i) tree.add(i , 1);
	for(auto x : g){
		// cout << x.second << ' ' << x.first << endl;
		ans += tree.sum(x.second - 1) - tree.sum(x.first);
		tree.add(x.second , -1);
		tree.add(x.first , -1);
	}
	return ans;
}

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