Submission #722834

#	Time	Username	Problem	Language	Result	Execution time	Memory
722834		becaido	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	3828 ms	716 KiB

dango3

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

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
namespace {

constexpr int Q_MAX = 50'000;
constexpr int NM_MAX = 10'000;

int N;
int M;
int C[NM_MAX + 1];

int query_count = 0;
int answer_count = 0;
bool finishes[NM_MAX + 1];

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}
}  // namespace

int Query(const vector<int> &x) {
  if (++query_count > Q_MAX) WrongAnswer(3);
  bool presents[NM_MAX + 1];
  for (int i = 1; i <= N * M; ++i) presents[i] = false;
  int colors[NM_MAX + 1];
  for (int i = 1; i <= N; i++) colors[i] = 0;
  for (const int t : x) {
    if (t <= 0 || t > N * M) WrongAnswer(1);
    if (presents[t]) WrongAnswer(2);
    presents[t] = true;
    colors[C[t]]++;
  }
  int color_min = M;
  for (int i = 1; i <= N; i++) {
    if (colors[i] < color_min) color_min = colors[i];
  }
  return color_min;
}

void Answer(const vector<int> &a) {
  ++answer_count;
  if ((int)a.size() != N) WrongAnswer(4);
  for (const int t : a) {
    if (t <= 0 || t > N * M) WrongAnswer(5);
    if (finishes[t]) WrongAnswer(6);
    finishes[t] = true;
  }
  int colors[NM_MAX + 1];
  for (int i = 1; i <= N; i++) colors[i] = 0;
  for (const int t : a) {
    colors[C[t]]++;
  }
  for (int i = 1; i <= N; i++) {
    if (colors[i] != 1) WrongAnswer(7);
  }
}
#endif

const int SIZE = 1e4 + 5;

namespace {

int sz;
bool vs[SIZE], is[SIZE];
int id[SIZE];

}  // namespace

int q_not(vector<int> v) {
    for (int x : v) is[x] = 1;
    vector<int> qv;
    FOR (i, 1, sz) if (!is[i]) qv.pb(i);
    for (int x : v) is[x] = 0;
    return Query(qv);
}

void Solve(int n, int m) {
    sz = n * m;
    fill(vs + 1, vs + sz + 1, 0);
    iota(id + 1, id + sz + 1, 1);
    mt19937 rng(time(NULL));
    FOR (t, 1, m) {
        shuffle(id + 1, id + sz + 1, rng);
        vector<int> v;
        FOR (i, 1, sz) if (!vs[id[i]] && v.size() < n) {
            v.pb(id[i]);
            int cnt = m - q_not(v);
            if (cnt != 1) v.pop_back();
        }
        Answer(v);
        for (int x : v) vs[x] = 1;
    }
}

#ifdef WAIMAI
int main() {
  if (scanf("%d%d", &N, &M) != 2) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  for (int i = 1; i <= N * M; ++i) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * M; ++i) finishes[i] = false;
  Solve(N, M);
  if (answer_count != M) WrongAnswer(8);
  printf("Accepted: %d\n", query_count);
  return 0;
}
#endif

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:107:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |         FOR (i, 1, sz) if (!vs[id[i]] && v.size() < n) {
      |                                          ~~~~~~~~~^~~

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