oj.uz

Submission #996339

# Submission time Handle Problem Language Result Execution time Memory
996339 2024-06-10T13:21:51 Z abczz Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2756 ms 12632 KB 
#include "dango3.h"
#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <algorithm>
#define ll int

using namespace std;

void Solve(int N, int M) {
  vector <ll> V[25], X;
  map <ll, ll> mp[25];
  ll l, r, mid, ret;
  for (int i=0; i<M; ++i) {
    for (int j=1; j<=N*M; ++j) ++mp[i][j];
  }
  for (int i=1; i<=N*M; ++i) {
    l = 0, r = M-1;
    while (l < r) {
      mid = (l+r)/2;
      X.clear();
      for (auto [x, y] : mp[mid]) {
        if (x != i) X.push_back(x);
      }
      ret = M-Query(X);
      if (ret > mid+1) l = mid+1;
      else r = mid;
    }
    V[l].push_back(i);
    for (int j=l; j<M; ++j) {
      mp[j].erase(i);
    }
  }
  /*for (int i=0; i<M; ++i) {
    for (auto u : V[i]) {
      cout << u << " ";
    }
    cout << endl;
  }*/
  for (int i=0; i<M; ++i) Answer(V[i]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 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 15 ms 860 KB Output is correct
2 Correct 14 ms 856 KB Output is correct
3 Correct 17 ms 860 KB Output is correct
4 Correct 17 ms 972 KB Output is correct
5 Correct 14 ms 860 KB Output is correct
6 Correct 13 ms 972 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 6428 KB Output is correct
2 Correct 459 ms 6232 KB Output is correct
3 Correct 702 ms 6488 KB Output is correct
4 Correct 670 ms 6232 KB Output is correct
5 Correct 427 ms 6232 KB Output is correct
6 Correct 436 ms 6432 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1824 ms 12144 KB Output is correct
2 Correct 1810 ms 12396 KB Output is correct
3 Correct 2756 ms 12632 KB Output is correct
4 Correct 2706 ms 12392 KB Output is correct
5 Correct 1647 ms 12380 KB Output is correct
6 Correct 1765 ms 12396 KB Output is correct