Submission #848042

#	Time	Username	Problem	Language	Result	Execution time	Memory
848042		NeroZein	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	1921 ms	1124 KiB

dango3

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

void Solve(int N, int M) {
  int mx = 0; 
  vector<vector<int>> ret(M + 1);
  vector<int> group(N * M + 1, M + 2);
  auto assign = [&](int i, int id) {
    group[i] = id;
    mx = max(mx, id); 
    ret[id].push_back(i);
  };
  auto ch = [&](int mid, int id) {
    vector<int> ask;
    for (int i = 1; i <= N * M; ++i) {
      if (group[i] >= mid && i != id) {
        ask.push_back(i); 
      }
    }
    int z = M - Query(ask); 
    return z == mid;
  }; 
  assign(1, 1); 
  for (int i = 2; i <= N * M; ++i) {
    int l = 1, r = mx + 1;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (ch(mid, i)) {
        l = mid;
      } else {
        r = mid - 1; 
      }
    }
    assign(i, l);
  }
  for (int i = 1; i <= M; ++i) {
    Answer(ret[i]); 
  }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78