Submission #996339

#	Time	Username	Problem	Language	Result	Execution time	Memory
996339		abczz	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2756 ms	12632 KiB

dango3

#include "dango3.h"
#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <algorithm>
#define ll int

using namespace std;

void Solve(int N, int M) {
  vector <ll> V[25], X;
  map <ll, ll> mp[25];
  ll l, r, mid, ret;
  for (int i=0; i<M; ++i) {
    for (int j=1; j<=N*M; ++j) ++mp[i][j];
  }
  for (int i=1; i<=N*M; ++i) {
    l = 0, r = M-1;
    while (l < r) {
      mid = (l+r)/2;
      X.clear();
      for (auto [x, y] : mp[mid]) {
        if (x != i) X.push_back(x);
      }
      ret = M-Query(X);
      if (ret > mid+1) l = mid+1;
      else r = mid;
    }
    V[l].push_back(i);
    for (int j=l; j<M; ++j) {
      mp[j].erase(i);
    }
  }
  /*for (int i=0; i<M; ++i) {
    for (auto u : V[i]) {
      cout << u << " ";
    }
    cout << endl;
  }*/
  for (int i=0; i<M; ++i) Answer(V[i]);
}

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