Submission #170683

#	Time	Username	Problem	Language	Result	Execution time	Memory
170683		youngyojun	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1082 ms	7420 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define rb(x) ((x)&(-(x)))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 200055;

struct BIT {
	int d[MAXN];

	void upd(int x, int r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	int get(int x) {
		int r = 0;
		for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

vector<int> BV[MAXN];
vector<pii> AV;

int A[MAXN];

ll Ans;
int N;

ll solve() {
	for(int i = 0; i < N*2; i++) {
		if(A[i] > 0) BV[A[i]].eb(i);
		else AV.eb(-A[i], i);
	}
	for(int i = 1; i <= N; i++) reverse(allv(BV[i]));

	for(int i = 0, x = 0, y; i < N; i++, x += 2) {
		y = AV[i].fi;
		Ans += x - AV[i].se + i*2 - bit.get(AV[i].se);
		bit.upd(AV[i].se, 1);
		Ans += x+1 - BV[y].back() + i*2+1 - bit.get(BV[y].back());
		bit.upd(BV[y].back(), 1);
		BV[y].pop_back();
	}
	return Ans;
}

long long count_swaps(std::vector<int> s) {
	N = sz(s)/2;
	for(int i = 0; i < N*2; i++) A[i] = s[i];

	for(; !s.empty();) {
		if(s[0] < 0) {
			int x = -s[0];
			s.erase(s.begin());
			int i = 0;
			for(; s[i] != x; i++);
			Ans += i;
			s.erase(s.begin() + i);
		} else {
			int x = s[0];
			int i = 0;
			for(; s[i] != -x; i++);
			Ans += i;
			s.erase(s.begin() + i);
			for(i = 0; s[i] != x; i++);
			Ans += i;
			s.erase(s.begin() + i);
		}
	}
	return Ans;
	return solve();
}

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