Submission #1161396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161396		fryingduc	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	533 ms	776 KiB

dango3

#include "dango3.h"
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

void dnc(int cnt, vector<int> cand) {
  if (cnt == 1) {
    Answer(cand);
    return;
  }
  int mid = (cnt + 1) / 2;
  vector<bool> vis((int)cand.size());
  vector<int> le;
  vector<int> ri;
  for (int i = 0; i < (int)cand.size(); ++i) {
    vector<int> ask;
    for (int j = 0; j < (int)cand.size(); ++j) {
      if (i != j and !vis[j]) {
        ask.push_back(cand[j]);
      }
    }
    if (Query(ask) >= mid) {
      vis[i] = 1;
      ri.push_back(cand[i]);
    } else {
      le.push_back(cand[i]);
    }
  }
  dnc(mid, le);
  dnc(cnt - mid, ri);
}

void Solve(int N, int M) {
  vector<int> cand(N * M);
  iota(cand.begin(), cand.end(), 1);
  dnc(M, cand);
}

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