제출 #628312

#제출 시각아이디문제언어결과실행 시간메모리
628312Kaitokid드문 곤충 (IOI22_insects)C++17
99.78 / 100
67 ms412 KiB
#include "insects.h" #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]; 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; if(ch(mid)){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; } */

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'bool ch(int)':
insects.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<g.size();i++)nt[g[i]]=true;
      |                     ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...