Submission #1264947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264947		mingga	Art Collections (BOI22_art)	C++20	0 / 100	0 ms	408 KiB

art

// Author: caption_mingle
#include "bits/stdc++.h"
#include "art.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;

struct BIT {
	int n;
	vector<int> bit;
	BIT(int n) : n(n) {
		bit.resize(n + 1, 0);
	}
	void update(int u, int x) {
		for(; u <= n; u += (u & -u)) bit[u] += x;
	}
	int get(int u) {
		int ans = 0;
		for(; u > 0; u -= (u & -u)) ans += bit[u];
		return ans;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};


void solve(int N) {
	vector<int> vec;
	for(int i = 1; i <= N; i++) vec.pb(i);
	int base = publish(vec);
	vector<int> f(N + 1, 0);
	for(int i = 2; i <= N; i++) {
		vector<int> vec;
		vec.pb(i);
		for(int j = 1; j <= N; j++) {
			if(j == i) continue;
			vec.pb(j);
		}
		int cur = publish(vec);
		f[i] = (i - 1 - base + cur) / 2;
	}
	vector<int> ans;
	BIT bit(N);
	for(int i = 1; i <= N; i++) bit.update(i, 1);
	for(int i = N; i > 0; i--) {
		int l = 1, r = N, tar;
		while(l <= r) {
			int m = (l + r) >> 1;
			if(bit.get(m, N) >= f[i] + 1) {
				tar = m;
				l = m + 1;
			} else r = m - 1;
		}
		ans.pb(tar);
		bit.update(tar, -1);
	}
	reverse(all(ans));
	answer(ans);
}

// signed main() {
// 	int n; cin >> n;
// 	solve(n);
// }

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