Submission #1185740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185740		nikaa123	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	1095 ms	2624 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 1e5+5;

int t[4*N];
int fix[N];
vector <vector <int>> v(N);

void update(int node, int tl, int tr,int pos) {
	if (tl == tr) {
		t[node]++;
		return;
	}
	int mid = (tl+tr)/2;
	if (pos <= mid) {
		update(node*2,tl,mid,pos);
	} else {
		update(node*2+1,mid+1,tr,pos);
	}
	t[node] = t[node*2]+t[node*2+1];
}

int getsum(int node, int tl, int tr, int l, int r) {
	if (l > r) return 0;
	if (tl == l && tr == r) {
		return t[node];
	}
	int mid = (tl+tr)/2;
	return (getsum(node*2,tl,mid,l,min(r,mid))+getsum(node*2+1,mid+1,tr,max(mid+1,l),r));
}

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	s.insert(s.begin(),0);
	for (int i = 1; i <= n; i++) {
		s[i] += n/2;
		v[s[i]].pb(i);
	}
	int op = 0;
	for (int i = 1; i <= n; i++) {
		if (fix[i]) continue;
		int a = s[i];
		int b;
		if (a <= n/2) {
			b = a+n/2;
		} else {
			b = a-n/2;
		}
		int l = 0; int r = v[b].size()-1;
		int ib;
		while (l <= r) {
			int mid = (l+r)/2;
			if (v[b][mid] > i) {
				ib = v[b][mid];
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		op += (ib-i-1-getsum(1,1,n,i,ib));
		update(1,1,n,ib);
		if (a > n/2) op++;
		fix[ib]++;
	}
	return op;
}

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