| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 838471 | Trumling | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
struct Trum
{
int l,r;
vector<int> here;
};
int min_cardinality(int N)
{
ll n=N;
vector<int>type(n,-1);
vector<int>count(n,1);
vector<int>v;
set<int>s;
for(int i=0;i<N;i++)
{
move_inside(i);
ll p=press_button();
if(p!=1)
move_outside(i);
else
{
type[i]=i;
s.insert(i);
v.pb(i);
}
}
Trum curr;
for(int i=0;i<N;i++)
if(type[i]==-1)
curr.here.pb(i);
queue<Trum>q;
curr.l=0;
curr.r=v.size()-1;
q.push(curr);
while(!q.empty())
{
curr=q.front();
q.pop();
if(curr.l==curr.r)
{
count[v[curr.l]]+=curr.here.size();
continue;
}
if(!curr.here.size())
continue;
ll mid=(curr.l+curr.r)/2;
for(int i=curr.l;i<=curr.r;i++)
{
if(i<=mid && s.find(v[i])==s.end())
{
move_inside(v[i]);
s.insert(v[i]);
}
if(i>mid && s.find(v[i])!=s.end())
{
move_outside(v[i]);
s.erase(v[i]);
}
}
Trum l,r;
l.l=curr.l;
l.r=mid;
r.l=mid+1;
r.r=curr.r;
for(auto x:curr.here)
{
move_inside(x);
ll p=press_button();
if(p!=1)
l.here.pb(x);
else
r.here.pb(x);
move_outside(x);
}
q.push(l);
q.push(r);
}
int ans=999999999;
for(auto x:v)
ans=min(count[x],ans);
return ans;
}
#include "insects.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <vector>
static inline constexpr int kMaxQueries = 40000;
static int N;
// Insect types are compressed to colors in the range [0, N).
static std::vector<int> color;
static std::vector<bool> in_box;
static std::vector<int> color_occurrences;
static std::multiset<int> max_occurrences;
static std::vector<int> op_counter(3, 0);
static inline void protocol_violation(std::string message) {
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
void move_inside(int i) {
if (i < 0 || i >= N) {
protocol_violation("invalid parameter");
}
++op_counter[0];
if (op_counter[0] > kMaxQueries) {
protocol_violation("too many calls");
}
if (!in_box[i]) {
in_box[i] = true;
max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
++color_occurrences[color[i]];
max_occurrences.insert(color_occurrences[color[i]]);
}
}
void move_outside(int i) {
if (i < 0 || i >= N) {
protocol_violation("invalid parameter");
}
++op_counter[1];
if (op_counter[1] > kMaxQueries) {
protocol_violation("too many calls");
}
if (in_box[i]) {
in_box[i] = false;
max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
--color_occurrences[color[i]];
max_occurrences.insert(color_occurrences[color[i]]);
}
}
int press_button() {
++op_counter[2];
if (op_counter[2] > kMaxQueries) {
protocol_violation("too many calls");
}
return *(max_occurrences.rbegin());
}
int main() {
assert(1 == scanf("%d", &N));
color.resize(N);
in_box.assign(N, false);
std::map<int, int> type_to_color;
for (int i = 0; i < N; ++i) {
int Ti;
assert(1 == scanf("%d", &Ti));
if (type_to_color.find(Ti) == type_to_color.end()) {
int new_color = type_to_color.size();
type_to_color[Ti] = new_color;
max_occurrences.insert(0);
}
color[i] = type_to_color[Ti];
}
color_occurrences.assign(type_to_color.size(), 0);
int answer = min_cardinality(N);
int Q = *std::max_element(op_counter.begin(), op_counter.end());
printf("%d\n", answer);
printf("%d\n", Q);
return 0;
}