제출 #1144266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144266		ind1v	사육제 (CEOI14_carnival)	C++17	0 / 100	4 ms	436 KiB

carnival

#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;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20