Submission #951356

#	Time	Username	Problem	Language	Result	Execution time	Memory
951356		kilkuwu	Carnival (CEOI14_carnival)	C++17	0 / 100	1 ms	456 KiB

carnival

#include <bits/stdc++.h>

#define nl '\n'

// std::mt19937_64 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937_64 rng(0); // Fixed seed
#define uid(a, b) std::uniform_int_distribution<long long>(a, b)(rng)

struct Judge {
  int N;
#ifdef LOCAL
  int C;
  std::vector<int> clothes;
#endif

#define INPUT 1

  int init() {
#ifdef LOCAL
    if (INPUT) {
      std::cin >> N;
      clothes.resize(N);
      for (int i = 0; i < N; i++) {
        std::cin >> clothes[i];
      }
    } else {
      N = uid(1, 10);
      C = uid(1, 5);
      for (int i = 0; i < N; i++) {
        clothes[i] = uid(1, C);
      }
    }
    return N;
#else 
    std::cin >> N;
    return N;
#endif
  }

  int ask(std::vector<int> friends) {
#ifdef LOCAL
    int bsz = friends.size();
    std::sort(friends.begin(), friends.end());
    friends.erase(std::unique(friends.begin(), friends.end()), friends.end());
    int asz = friends.size();
    assert(asz == bsz);
    std::set<int> s;
    for (int i : friends) {
      assert(0 <= i && i < N);
      s.insert(clothes[i]);
    }
    return s.size();
#else 
    std::cout << friends.size() << " ";
    for (int i : friends) std::cout << ++i << " ";
    std::cout << std::endl;
    int ans; std::cin >> ans;
    return ans;
#endif
  }

  void answer(const std::vector<int>& costumes) {
#ifdef LOCAL
    assert(costumes.size() == clothes.size());
    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int i, int j) {
      return clothes[i] < clothes[j];
    });

    for (int i = 0; i < N; i++) {
      if (i > 0) {
        assert(costumes[ord[i]] != costumes[ord[i - 1]]);
      }
      int j = i;
      while (j < N && clothes[ord[i]] == clothes[ord[j]]) {
        assert(costumes[ord[i]] == costumes[ord[j]]);
        j++;
      }
      i = j - 1;
    }
    std::cout << "CORRECT ANSWER" << std::endl;
#else
    std::cout << 0 << " ";
    for (int i = 0; i < N; i++) {
      std::cout << costumes[i] + 1 << " ";
    }
    std::cout << std::endl;
#endif
  }
} judge;

std::vector<int> combine(std::vector<int> l, const std::vector<int>& r) {
  l.insert(l.end(), r.begin(), r.end());
  return l;
}

std::vector<int> subvec(const std::vector<int>& a, int l, int r) {
  std::vector<int> res(r - l + 1);
  for (int i = l; i <= r; i++) {
    res[i - l] = a[i];
  }
  return res;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);


  int N = judge.init();

  std::vector<int> answer(N);
  answer[0] = 0;
  std::vector<int> colors;
  colors.push_back(0);
  for (int i = 1; i < N; i++) {
    int res = judge.ask(combine(colors, {i}));
    if (res > (int) colors.size()) {
      answer[i] = colors.size();
      colors.push_back(i);
      continue;
    }

    int lb = 0, rb = i - 1;
    while (lb < rb) {
      int mid = (lb + rb) / 2;

      res = judge.ask(combine(subvec(colors, 0, mid), {i}));
      if (res == mid + 1) {
        rb = mid;
      } else {
        lb = mid + 1; // we aint have it here
      }
    } 

    answer[i] = colors[rb];
  }

  judge.answer(answer);

}      

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