제출 #831321

#제출 시각아이디문제언어결과실행 시간메모리
831321definitelynotmee드문 곤충 (IOI22_insects)C++17
88.31 / 100
90 ms492 KiB
#include "insects.h" #include<bits/stdc++.h> #define all(x) x.begin(), x.end() using ll = long long; using namespace std; template<typename T> using matrix = vector<vector<T>>; const double coef_bin_search = 0.42, coef_sqrt = 0.13; struct Machine { set<int> s; void insert(int id){ s.insert(id); move_inside(id); } void erase(int id){ s.erase(id); move_outside(id); } int resp(){ return press_button(); } void clear(){ auto it = s.begin(); while(it!=s.end()){ move_outside(*it); it = s.erase(it); } } }; int min_cardinality(int N) { mt19937 rng(time(nullptr)); vector<int> dif; vector<int> resto; Machine m; for(int i = 0; i < N; i++){ m.insert(i); if(m.resp() == 1){ dif.push_back(i); } else m.erase(i), resto.push_back(i); } shuffle(all(dif),rng); shuffle(all(resto),rng); m.clear(); if(dif.size() > N*coef_sqrt/dif.size()){ int ini = 1, fim = N/dif.size(); auto putless =[&](int mx){ for(int i : resto){ if(m.s.count(i)) continue; m.insert(i); if(m.resp() > mx) m.erase(i); } }; int last = -1; while(ini!=fim){ int mid = (fim-ini)*coef_bin_search+ini; while(mid <= ini) mid++; // cerr << "mid = " << mid << '\n'; if(mid < last) m.clear(); putless(mid-1); bool ok = 1; for(int i : dif){ m.insert(i); ok&= m.resp() == mid; m.erase(i); } if(ok) ini = mid; else fim = mid-1; last = mid; } return ini; } else { int resp = N; auto dq =[&](vector<int> dif, vector<int> resto, bool flag, auto dq) -> void { if(dif.size() == 1 || resto.size() == 0){ resp = min(resp,(int)resto.size()); return; } int mid = dif.size()/2; if(flag){ for(int i = mid; i < dif.size(); i++) m.erase(dif[i]); } else{ for(int i = 0; i < mid; i++){ m.insert(dif[i]); } } vector<int> ldif, rdif, lresto, rresto; for(int i = 0; i < mid; i++) ldif.push_back(dif[i]); for(int i = mid; i < dif.size(); i++) rdif.push_back(dif[i]); for(int i : resto){ m.insert(i); if(m.resp() == 2) lresto.push_back(i); else rresto.push_back(i); m.erase(i); } dq(ldif,lresto,1,dq); m.clear(); dq(rdif,rresto,0,dq); }; dq(dif,resto,0,dq); return resp+1; } }

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

insects.cpp: In lambda function:
insects.cpp:109:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int i = mid; i < dif.size(); i++)
      |                                  ~~^~~~~~~~~~~~
insects.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i = mid; i < dif.size(); i++)
      |                              ~~^~~~~~~~~~~~
insects.cpp: In instantiation of 'min_cardinality(int)::<lambda(std::vector<int>, std::vector<int>, bool, auto:23)> [with auto:23 = min_cardinality(int)::<lambda(std::vector<int>, std::vector<int>, bool, auto:23)>]':
insects.cpp:139:26:   required from here
insects.cpp:109:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int i = mid; i < dif.size(); i++)
      |                                  ~~^~~~~~~~~~~~
insects.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i = mid; i < dif.size(); i++)
      |                              ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...