oj.uz

Submission #544845

# Submission time Handle Problem Language Result Execution time Memory
544845 2022-04-02T20:21:23 Z MarcoMeijer Super Dango Maker (JOI22_dango3) C++17
100 / 100
 5171 ms 12228 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int query(set<int>& st) {
  vector<int> a;
  for (int x : st) a.push_back(x);
  return Query(a);
}

}  // namespace

void Solve(int N, int M) {
  vector<vector<int>> byGroup;
  vector<set<int>> notInGroups;
  byGroup.resize(M);
  notInGroups.resize(M);
  for (int i=0; i<M; i++)
    for (int j=1; j<=N*M; j++)
      notInGroups[i].insert(j);

  for (int i=1; i<=N*M; i++) {
    int lb=0, ub=M-1;
    while (lb != ub) {
      int mid=(lb+ub+1)/2;
      notInGroups[mid].erase(i);
      int res = query(notInGroups[mid]);
      notInGroups[mid].insert(i);
      if (res >= M - mid) ub = mid-1;
      else lb = mid;
    }
    byGroup[lb].push_back(i);
    for (int j=lb+1; j<M; j++)
      notInGroups[j].erase(i);
  }

  for (int i=0; i<M; i++) {
    Answer(byGroup[i]);
  }
}

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 724 KB Output is correct
2 Correct 27 ms 724 KB Output is correct
3 Correct 34 ms 724 KB Output is correct
4 Correct 34 ms 724 KB Output is correct
5 Correct 26 ms 828 KB Output is correct
6 Correct 26 ms 852 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 6288 KB Output is correct
2 Correct 797 ms 6284 KB Output is correct
3 Correct 1205 ms 6292 KB Output is correct
4 Correct 1219 ms 6284 KB Output is correct
5 Correct 712 ms 6284 KB Output is correct
6 Correct 742 ms 6292 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 3165 ms 12228 KB Output is correct
2 Correct 3114 ms 12228 KB Output is correct
3 Correct 5083 ms 12228 KB Output is correct
4 Correct 5171 ms 12228 KB Output is correct
5 Correct 2892 ms 12224 KB Output is correct
6 Correct 2889 ms 12220 KB Output is correct