| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1144265 | ind1v | 사육제 (CEOI14_carnival) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 155;
struct fenwick_tree {
int f[N];
fenwick_tree() {
memset(f, 0, sizeof(f));
}
void upd(int i, int x) {
for (; i < N; i += i & -i) {
f[i] += x;
}
}
int get(int i) {
int r = 0;
for (; i > 0; i -= i & -i) {
r += f[i];
}
return r;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
struct dsu {
int lab[N];
dsu() {
memset(lab, -1, sizeof(lab));
}
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool merge(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return false;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
int n;
int c[N];
fenwick_tree ft;
dsu g;
int ask(int l, int r) {
cout << r - l + 1 << ' ';
for (int i = l; i <= r; i++) {
cout << i << ' ';
}
cout << endl;
int res;
cin >> res;
return res;
}
void answer() {
cout << 0 << ' ';
for (int i = 1; i <= n; i++) {
cout << c[i] << ' ';
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int prv = 0;
for (int i = 1; i <= n; i++) {
int res = ask(1, i);
ft.upd(i, 1);
if (res == prv + 1) {
prv = res;
continue;
} else {
prv = res;
int lo = 1, hi = i, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (ft.get(mid, i) == ask(mid, i)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ans--;
ft.upd(ans, -1);
g.merge(ans, i);
}
}
vector<int> v;
for (int i = 1; i <= n; i++) {
c[i] = g.find(i);
v.emplace_back(c[i]);
}
sort(v.begin(), v.end));
for (int i = 1; i <= n; i++) {
c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin() + 1;
}
answer();
return 0;
}