| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 628302 | Kaitokid | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
/*vector<int>A;
int fr[20009];
int cnt[3];
void move_inside(int x)
{
cnt[0]++;
cout<<"in "<<x<<endl;
fr[A[x]]++;
}
void move_outside(int x)
{
cnt[1]++;
cout<<"out "<<x<<endl;
fr[A[x]]--;
}
int press_button()
{
cnt[2]++;
cout<<"press"<<endl;
int res=0;
for(int i=0;i<2000;i++)res=max(res,fr[i]);
return res;
}*/
int n,dst;
stack<int>st;
bool nt[20009];
/*inline bool ch(int x)
{
while(!st.empty()){move_outside(st.top());st.pop();}
int sz=0;
vector<int>g;
for(int i=0;i<n;i++)
{
if(nt[i])continue;
if(sz==0){st.push(i);move_inside(i);sz++;continue;}
move_inside(i);
if(press_button()>x){move_outside(i);g.push_back(i);continue;}
sz++;
st.push(i);
}
if(sz==x*dst)
{
while(!st.empty()){nt[st.top()]=true;move_outside(st.top());st.pop();}
return true;
}
for(int i=0;i<g.size();i++)nt[g[i]]=true;
return false;
}*/
int rss;
int min_cardinality(int N)
{
rss=0;
n=N;
dst=0;
move_inside(0);
st.push(0);
dst++;
for(int i=1;i<n;i++)
{
move_inside(i);
if(press_button()==1){st.push(i);dst++;}
else move_outside(i);
}
int l=1,r=n/dst;
while(l<r)
{
int mid=(l+r+1)/2;
int x=mid;
bool bl;
while(!st.empty()){move_outside(st.top());st.pop();}
int sz=0;
vector<int>g;
for(int i=0;i<n;i++)
{
if(nt[i])continue;
if(sz==0){st.push(i);move_inside(i);sz++;continue;}
move_inside(i);
if(press_button()>x){move_outside(i);g.push_back(i);continue;}
sz++;
st.push(i);
}
if(sz==x*dst)
{
while(!st.empty()){nt[st.top()]=true;move_outside(st.top());st.pop();}
bl=true;
}else {
for(int i=0;i<g.size();i++)nt[g[i]]=true;
bl=false;
}
if(bl){l=0;r-=mid;rss+=mid;}
else r=mid-1;
}
return l+rss;
}
/*
int main()
{
A={5,8,9,5,9,9};
cout<<min_cardinality(6)<<endl;
cout<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl;
return 0;
}
*/