이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "insects.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
int min_cardinality(int n)
{
// i번 원소는 각 집합에서 l[i]번째 이상 r[i]번째 이하 원소임(맨왼쪽부터 그 집합 순서대로 다 포함시켰을때)
vector<int> l(n, 1);
vector<int> r(n, n);
set<int> sel;
for (int i = 0; i < n; i++)
{
move_inside(i);
if (press_button() > 1)
{
l[i] = 2;
move_outside(i);
continue;
}
l[i] = r[i] = 1;
sel.insert(i);
}
int group = sel.size();
int now = 1;
int lo = 1, hi = n / group;
int ans = n;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
set<int> noSel;
for (auto& si : sel)
{
if (l[si] > mid)
noSel.insert(si);
}
for (auto& no : noSel)
{
move_outside(no);
sel.erase(no);
}
now = press_button();
for (int i = 0; i < n; i++)
{
if (sel.find(i) != sel.end())
continue;
move_inside(i);
int x = press_button();
if (x > mid)
{
l[i] = x;
move_outside(i);
continue;
}
if (x > now)
{
l[i] = r[i] = x;
now = x;
}
else
{
// 최소한 now번째 이하임
r[i] = now;
l[i] = min(l[i], r[i]);
}
}
if (sel.size() == group * mid)
{
ans = mid;
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:105:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | if (sel.size() == group * mid)
| ~~~~~~~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |