Submission #944338

#	Time	Username	Problem	Language	Result	Execution time	Memory
944338		nguyentunglam	Minerals (JOI19_minerals)	C++17	100 / 100	38 ms	4828 KiB

minerals

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

const int NN = 1e5 + 10;

int f[NN], g[NN], n;

void dnc (vector<int> one, vector<int> two, bool toggle) {
  if (one.size() == 1) {
    Answer(one[0], two[0]);
    return;
  }
  int sz = g[one.size()], cur = 0;
  assert(one.size() == two.size());
  assert(sz < one.size());
  vector<int> one_left, one_right, two_left, two_right;
  for(int i = 0; i < one.size(); i++) {
    if (i < sz) one_left.push_back(one[i]);
    else one_right.push_back(one[i]);
  }
  for(int i = 0; i < sz; i++) cur = Query(one[i]);
  for(int i = 0; i + 1 < two.size(); i++) {
    int nxt = Query(two[i]);
    if (cur != nxt) {
      two_left.push_back(two[i]);
      cur = nxt;
    }
    else two_right.push_back(two[i]);
  }
  if (!toggle) swap(two_left, two_right);
  if (two_left.size() < sz) two_left.push_back(two.back());
  else two_right.push_back(two.back());
  dnc(one_left, two_left, toggle ^ 1);
  dnc(one_right, two_right, toggle);
}

void Solve(int N) {
  n = N;
  for(int i = 2; i <= n; i++) {
    f[i] = 1e9;
    int l = 1, r = i / 2;
    auto cost = [&] (int j) {
      return f[j] + f[i - j] + j + i - 1;
    };
    while (l < r) {
      int mid = l + r >> 1;
      if (cost(mid) <= cost(mid + 1)) r = mid;
      else l = mid + 1;
    }
    f[i] = cost(l);
    g[i] = l;
  }
//  for(int i = 2; i <= n; i++) cout << g[i] << endl;
//  exit(0);

  int cur = 0;
  vector<int> one, two;
  for(int i = 1; i <= 2 * n; i++) {
    if (Query(i) > cur) {
      cur++;
      one.push_back(i);
    }
    else two.push_back(i);
  }
  dnc(one, two, 1);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minerals.cpp:2:
minerals.cpp: In function 'void dnc(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:16:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   assert(sz < one.size());
      |          ~~~^~~~~~~~~~~~
minerals.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < one.size(); i++) {
      |                  ~~^~~~~~~~~~~~
minerals.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i = 0; i + 1 < two.size(); i++) {
      |                  ~~~~~~^~~~~~~~~~~~
minerals.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |   if (two_left.size() < sz) two_left.push_back(two.back());
      |       ~~~~~~~~~~~~~~~~^~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10