oj.uz

Submission #547568

# Submission time Handle Problem Language Result Execution time Memory
547568 2022-04-11T01:17:41 Z SuffixAutomata Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2372 ms 1480 KB 
#include "dango3.h"

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

namespace {
int n, m;
}

void dfs(vector<int> cur) {
  if (cur.size() == n)
    return Answer(cur);
  int targ = cur.size() / n / 2;
  set<int> cur2(all(cur)), cur3;
  auto it = cur2.begin();
  while (cur2.size() != targ * n) {
    int v = *it;
    it = cur2.erase(it);
    if (Query(vector<int>(all(cur2))) >= targ)
      cur3.insert(v);
    else
      cur2.insert(v);
  }
  dfs(vector<int>(all(cur2)));
  dfs(vector<int>(all(cur3)));
}

void Solve(int N, int M) {
  n = N, m = M;
  vector<int> remain;
  for (int i = 0; i < M; i++)
    for (int j = 0; j < N; j++)
      remain.push_back(N * i + j + 1);
  dfs(remain);
}

Compilation message

dango3.cpp: In function 'void dfs(std::vector<int>)':
dango3.cpp:22:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   if (cur.size() == n)
      |       ~~~~~~~~~~~^~~~
dango3.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   while (cur2.size() != targ * n) {
      |          ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 428 KB Output is correct
2 Correct 18 ms 416 KB Output is correct
3 Correct 22 ms 468 KB Output is correct
4 Correct 22 ms 460 KB Output is correct
5 Correct 13 ms 468 KB Output is correct
6 Correct 14 ms 492 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 888 KB Output is correct
2 Correct 430 ms 880 KB Output is correct
3 Correct 585 ms 888 KB Output is correct
4 Correct 576 ms 904 KB Output is correct
5 Correct 326 ms 792 KB Output is correct
6 Correct 320 ms 908 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 1408 KB Output is correct
2 Correct 1787 ms 1432 KB Output is correct
3 Correct 2337 ms 1340 KB Output is correct
4 Correct 2372 ms 1480 KB Output is correct
5 Correct 1294 ms 1468 KB Output is correct
6 Correct 1265 ms 1408 KB Output is correct