제출 #1351876

#제출 시각아이디문제언어결과실행 시간메모리
1351876avighnaSuper Dango Maker (JOI22_dango3)C++20
22 / 100
917 ms696 KiB
#include <bits/stdc++.h>

using namespace std;

int Query(const vector<int> &x);
void Answer(const vector<int> &a);

void Solve(int N, int M) {
  // we will identify all colors with a binary search first
  // query(prefix) = 00000001
  // that first 1 means its the first occurence of some color
  // then we remove it, do binary search again, that'll find the second occurence, and so on
  vector<vector<int>> occs(N + 1);
  vector<int> active(N * M);
  iota(active.begin(), active.end(), 1);
  for (int i = 1; i <= N; ++i) {
    set<int> curs;
    const int tot = active.size();
    int idx = -1;
    while (idx != tot) {
      idx = *ranges::partition_point(views::iota(idx + 1, tot), [&](int idx) {
        vector<int> b;
        for (auto &i : occs) {
          for (auto &j : i) {
            b.push_back(j);
          }
        }
        for (int i = 0; i <= idx; ++i) {
          if (!curs.contains(active[i])) {
            b.push_back(active[i]);
          }
        }
        return Query(b) == 0;
      });
      if (idx == tot) {
        break;
      }
      curs.insert(active[idx]);
    }
    occs[i] = vector<int>(curs.begin(), curs.end());
    vector<int> nactive;
    for (int &i : active) {
      if (!curs.contains(i)) {
        nactive.push_back(i);
      }
    }
    active = nactive;
  }

  for (int i = 0; i < M; ++i) {
    vector<int> ans;
    for (int j = 1; j <= N; ++j) {
      ans.push_back(occs[j][i]);
    }
    Answer(ans);
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...