Submission #629128

#TimeUsernameProblemLanguageResultExecution timeMemory
629128urd05Rarest Insects (IOI22_insects)C++17
0 / 100
1 ms336 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; vector<int> v; bool in[2000]; bool vis[2000]; int mnv; int val; int n; int mi(int i) { in[i]=true; move_inside(v[i]); } int 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; 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 { save.push_back(i); } } 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>=2) { 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=(lo+hi)/2; if (isp(mid)) { lo=mid; } else { hi=mid; } } return lo; }

Compilation message (stderr)

insects.cpp: In function 'int mi(int)':
insects.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
   15 | }
      | ^
insects.cpp: In function 'int mo(int)':
insects.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | }
      | ^
insects.cpp: In function 'bool isp(int)':
insects.cpp:70:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     if (save.size()==x*val) {
      |         ~~~~~~~~~~~^~~~~~~
insects.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i=0;i<save.size();i++) {
      |                     ~^~~~~~~~~~~~
insects.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<out.size();i++) {
      |                 ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...