제출 #629464

#제출 시각아이디문제언어결과실행 시간메모리
629464urd05드문 곤충 (IOI22_insects)C++17
10 / 100
353 ms536 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; vector<int> v; bool in[2000]; bool vis[2000]; int mnv=1; int val; int n; void mi(int i) { in[i]=true; move_inside(v[i]); } void mo(int i) { in[i]=false; move_outside(v[i]); } int pb() { return press_button(); } void clean() { for(int i=0;i<n;i++) { if (in[i]) { mo(i); } } } int f() { int ret=0; for(int i=0;i<n;i++) { mi(i); int got=pb(); if (got>1) { mo(i); } else { vis[i]=true; ret++; } } clean(); return ret; } bool isp(int x) { x-=mnv; vector<int> save; vector<int> out; int pr=0; for(int i=0;i<n;i++) { if (vis[i]) { continue; } mi(i); int got=pb(); if (got>x) { mo(i); out.push_back(i); } else { if (pr==x-1&&got==x) { out.push_back(i); } save.push_back(i); } pr=got; } clean(); if (save.size()==x*val) { for(int i=0;i<save.size();i++) { vis[save[i]]=true; } mnv+=x; return true; } for(int i=0;i<out.size();i++) { vis[out[i]]=true; } return false; } int min_cardinality(int N) { n=N; for(int i=0;i<n;i++) { v.push_back(i); } srand(int(time(NULL))); random_shuffle(v.begin(),v.end()); val=f(); if (val<4) { memset(vis,0,sizeof(vis)); int sum=n; int ret=n; for(int i=0;i<val-1;i++) { int now=0; while (vis[now]) { now++; } mi(now); vis[now]=true; now++; int cnt=1; while (now<n) { while (now<n&&vis[now]) { now++; } if (now>=n) { break; } mi(now); int got=pb(); if (got==cnt) { mo(now); } else { vis[now]=true; cnt++; } now++; } clean(); ret=min(ret,cnt); sum-=cnt; } return min(sum,ret); } int lo=1; //ans>=lo int hi=n/val+1; //ans<hi while (lo+1<hi) { int mid; int left; for(int i=0;i<n;i++) { if (!vis[i]) { left++; } } mid=mnv+left/(2*val); if (mid<=lo) { mid=lo+1; } if (mid>=hi) { mid=hi-1; } if (isp(mid)) { lo=mid; } else { hi=mid; } } return lo; }

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

insects.cpp: In function 'bool isp(int)':
insects.cpp:75:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     if (save.size()==x*val) {
      |         ~~~~~~~~~~~^~~~~~~
insects.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<save.size();i++) {
      |                     ~^~~~~~~~~~~~
insects.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<out.size();i++) {
      |                 ~^~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:140:15: warning: 'left' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |           left++;
      |           ~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...