이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
컴파일 시 표준 에러 (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;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |