제출 #1150892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150892		gyg	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	205 ms	31268 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 2e5 + 5;

int n;
arr<int, N> a;

arr<int, N> prm;
void prm_cmp() {
	map<int, vec<int>> ng, ps;
	for (int i = 1; i <= n; i++) {
		if (a[i] < 0) ng[-a[i]].push_back(i);
		else ps[a[i]].push_back(i);
	}

	vec<pii> ord;
	for (pair<int, vec<int>> x : ng) 
		for (int i = 0; i < x.sec.size(); i++)
			ord.push_back({x.sec[i], ps[x.fir][i]});

	auto cmp = [](pii x, pii y) {
		return min(x.fir, x.sec) < min(y.fir, y.sec);
	};
	sort(ord.begin(), ord.end(), cmp);

	for (int i = 0; i < ord.size(); i++)
		prm[ord[i].fir] = 2 * i + 1, prm[ord[i].sec] = 2 * i + 2;
}

struct Sgt {
	arr<int, 4 * N> sg;
	void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
		if (lw == hg) { sg[u] += x; return; }
		int md = (lw + hg) / 2;
		if (i <= md) upd(i, x, 2 * u, lw, md);
		else upd(i, x, 2 * u + 1, md + 1, hg); 
		sg[u] = sg[2 * u] + sg[2 * u + 1];
	}
	int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
		if (l > r) return 0;
		if (l <= lw && hg <= r) return sg[u];
		int md = (lw + hg) / 2, ans = 0;
		if (l <= md) ans += qry(l, r, 2 * u, lw, md);
		if (r > md) ans += qry(l, r, 2 * u + 1, md + 1, hg);
		return ans;
	}
} sgt;

int ans_cmp() {
	int ans = 0;
	for (int i = n; i >= 1; i--) {
		ans += sgt.qry(1, prm[i] - 1);
		sgt.upd(prm[i], +1);
	}
	return ans;
}

int count_swaps(vec<sig> _a) {
	n = _a.size();
	for (int i = 1; i <= n; i++) a[i] = _a[i - 1];

	prm_cmp();
	int ans = ans_cmp();

	// for (int i = 1; i <= n; i++) cout << i << ": " << prm[i] << '\n';

	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