oj.uz

Submission #951713

# Submission time Handle Problem Language Result Execution time Memory
951713 2024-03-22T11:30:54 Z qwe1rt1yuiop1 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 154 ms 852 KB 
#include "dango3.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

namespace
{
  int variable_example = 1;
} // namespace

mt19937 rng(48763);

void Solve(int n, int m)
{
  vector<int> flag(n * m, 1);

  for (int ii = 0; ii < m; ++ii)
  {
    vector<int> todo;
    for (int i = 1; i <= n * m; ++i)
      if (flag[i - 1])
        todo.emplace_back(i);
    shuffle(all(todo), rng);

    int l = n, r = sz(todo);
    while (l < r)
    {
      int mid = (l + r) >> 1;
      vector<int> v;
      for (int i = 0; i < mid; ++i)
        v.emplace_back(todo[i]);
      if (Query(v))
        r = mid;
      else
        l = mid + 1;
    }
    vector<int> ans;
    for (int i = 0; i < l; ++i)
    {
      auto ans0 = ans;
      for (int j = i + 1; j < l; ++j)
        ans.emplace_back(todo[j]);
      if (Query(ans) == 0)
        ans0.emplace_back(todo[i]);
      ans = ans0;
    }
    Answer(ans);
    for (int i : ans)
      flag[i - 1] = 0;
  }
}

/*
3 2
3 3 1 2 1 2

*/

Compilation message

dango3.cpp:9:7: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    9 |   int variable_example = 1;
      |       ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 532 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 604 KB Output is correct
2 Correct 34 ms 604 KB Output is correct
3 Correct 30 ms 604 KB Output is correct
4 Correct 35 ms 852 KB Output is correct
5 Correct 31 ms 600 KB Output is correct
6 Correct 36 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 732 KB Output is correct
2 Correct 128 ms 728 KB Output is correct
3 Correct 154 ms 852 KB Output is correct
4 Correct 143 ms 728 KB Output is correct
5 Correct 137 ms 604 KB Output is correct
6 Correct 127 ms 604 KB Output is correct