Submission #547568

#	Time	Username	Problem	Language	Result	Execution time	Memory
547568		SuffixAutomata	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2372 ms	1480 KiB

dango3

#include "dango3.h"

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

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

namespace {
int n, m;
}

void dfs(vector<int> cur) {
  if (cur.size() == n)
    return Answer(cur);
  int targ = cur.size() / n / 2;
  set<int> cur2(all(cur)), cur3;
  auto it = cur2.begin();
  while (cur2.size() != targ * n) {
    int v = *it;
    it = cur2.erase(it);
    if (Query(vector<int>(all(cur2))) >= targ)
      cur3.insert(v);
    else
      cur2.insert(v);
  }
  dfs(vector<int>(all(cur2)));
  dfs(vector<int>(all(cur3)));
}

void Solve(int N, int M) {
  n = N, m = M;
  vector<int> remain;
  for (int i = 0; i < M; i++)
    for (int j = 0; j < N; j++)
      remain.push_back(N * i + j + 1);
  dfs(remain);
}

Compilation message (stderr)

dango3.cpp: In function 'void dfs(std::vector<int>)':
dango3.cpp:22:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   if (cur.size() == n)
      |       ~~~~~~~~~~~^~~~
dango3.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   while (cur2.size() != targ * n) {
      |          ~~~~~~~~~~~~^~~~~~~~~~~

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