Submission #679811

#	Time	Username	Problem	Language	Result	Execution time	Memory
679811		peijar	Carnival (CEOI14_carnival)	C++17	100 / 100	9 ms	324 KiB

carnival

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int lb, int ub) {
  return uniform_int_distribution<int>(lb, ub)(rng);
}

const bool LOCAL = 0;

vector<int> types;

int makeQuery(vector<int> &people) {
  if (LOCAL) {
    set<int> s;
    for (int x : people)
      s.insert(types[x]);
    return s.size();
  } else {
    cout << people.size() << endl;
    for (int x : people)
      cout << x + 1 << ' ';
    cout << endl;
    int ret;
    cin >> ret;
    return ret;
  }
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n;
  if (LOCAL) {
    n = randint(2, 10);
    types.resize(n);
    int C = randint(1, n);
    for (int i = 0; i < n; ++i)
      types[i] = randint(1, C);
    dbg(n, types);
  } else
    cin >> n;

  vector<int> curCC;
  vector<int> sol(n);
  curCC.push_back(0);
  for (int u = 1; u < n; ++u) {
    curCC.push_back(u);
    int q = makeQuery(curCC);
    if (q == (int)curCC.size()) {
      sol[u] = curCC.size() - 1;
      continue;
    }
    curCC.pop_back();

    int lo = 0, up = (int)curCC.size() - 1;
    while (lo < up) {
      int mid = (lo + up) / 2;
      vector<int> ccs;
      for (int i = lo; i <= mid; ++i)
        ccs.push_back(curCC[i]);
      ccs.push_back(u);
      if (makeQuery(ccs) == (int)ccs.size())
        lo = mid + 1;
      else
        up = mid;
    }
    sol[u] = lo;
  }
  if (LOCAL) {
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        assert((types[i] == types[j]) == (sol[i] == sol[j]));
  }
  cout << 0;
  for (int x : sol)
    cout << ' ' << x + 1;
  cout << endl;
}

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