oj.uz

Submission #848042

# Submission time Handle Problem Language Result Execution time Memory
848042 2023-09-11T07:15:19 Z NeroZein Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1921 ms 1124 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

void Solve(int N, int M) {
  int mx = 0; 
  vector<vector<int>> ret(M + 1);
  vector<int> group(N * M + 1, M + 2);
  auto assign = [&](int i, int id) {
    group[i] = id;
    mx = max(mx, id); 
    ret[id].push_back(i);
  };
  auto ch = [&](int mid, int id) {
    vector<int> ask;
    for (int i = 1; i <= N * M; ++i) {
      if (group[i] >= mid && i != id) {
        ask.push_back(i); 
      }
    }
    int z = M - Query(ask); 
    return z == mid;
  }; 
  assign(1, 1); 
  for (int i = 2; i <= N * M; ++i) {
    int l = 1, r = mx + 1;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (ch(mid, i)) {
        l = mid;
      } else {
        r = mid - 1; 
      }
    }
    assign(i, l);
  }
  for (int i = 1; i <= M; ++i) {
    Answer(ret[i]); 
  }
}

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 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 14 ms 344 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 12 ms 344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 592 KB Output is correct
2 Correct 362 ms 592 KB Output is correct
3 Correct 482 ms 608 KB Output is correct
4 Correct 486 ms 596 KB Output is correct
5 Correct 301 ms 572 KB Output is correct
6 Correct 295 ms 344 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 1124 KB Output is correct
2 Correct 1431 ms 912 KB Output is correct
3 Correct 1921 ms 1112 KB Output is correct
4 Correct 1917 ms 708 KB Output is correct
5 Correct 1184 ms 672 KB Output is correct
6 Correct 1205 ms 676 KB Output is correct