oj.uz

Submission #848041

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

namespace {
int variable_example = 1;
}

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); 
    //cout << "Z: " << z << ' ' << mid << '\n';
    //cout << "ASK: ";
    //for (int i : ask) cout << i << ' ';
    //cout << '\n'; 
    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; 
      }
    }
    //cout << i << ' ' << l << '\n';
    assign(i, l);
  }
  for (int i = 1; i <= M; ++i) {
    Answer(ret[i]); 
  }
}

Compilation message

dango3.cpp:6:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    6 | 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 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 11 ms 348 KB Output is correct
3 Correct 14 ms 508 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 10 ms 504 KB Output is correct
6 Correct 10 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 608 KB Output is correct
2 Correct 352 ms 600 KB Output is correct
3 Correct 494 ms 604 KB Output is correct
4 Correct 486 ms 848 KB Output is correct
5 Correct 298 ms 600 KB Output is correct
6 Correct 299 ms 844 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1451 ms 744 KB Output is correct
2 Correct 1509 ms 968 KB Output is correct
3 Correct 1927 ms 1008 KB Output is correct
4 Correct 1929 ms 988 KB Output is correct
5 Correct 1194 ms 716 KB Output is correct
6 Correct 1219 ms 708 KB Output is correct