제출 #1357842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357842		retarde	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	1246 ms	1308 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

namespace {

int variable_example = 1;
int n, m;

}  // namespace

int func(vector<int>& exc) {
  vector<int> pres(n * m, 1);
  for (auto &x : exc) pres[x] = 0;
  vector<int> qry; for (int i = 0; i < n*m; i++) if (pres[i]) qry.push_back(i + 1);
  return Query(qry);
}

void Solve(int N, int M) {
  n = N; m = M;
  vector<vector<int>> dango(M); dango[0].push_back(0);
  for (int i = 1; i < N*M; i++) {
    int lo = -1; int hi = M - 1;
    while (hi > lo + 1) {
      int mid = (lo + hi) / 2;
      vector<int> excl; excl.push_back(i);
      for (auto &x : dango[mid]) excl.push_back(x);
      int q = func(excl);
      if (q == M - 1) {
        // he wanst part
        hi = mid;
      } else {
        lo = mid;
        // he was part
      }
    }

    dango[hi].push_back(i);
  }

  for (auto &x : dango) {
    for (auto &y : x) y++;
    Answer(x);
  }
}

• 서브태스크 1: 2 / 2
• 서브태스크 2: 5 / 5
• 서브태스크 3: 15 / 15
• 서브태스크 4: 78 / 78