Submission #742660

#TimeUsernameProblemLanguageResultExecution timeMemory
742660dooweyRarest Insects (IOI22_insects)C++17
93.05 / 100
92 ms548 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int gen(int m){ return ((int)rng() % m + m) % m; } int min_cardinality(int n) { int val; set<int> in; vector<int> cand; for(int i = 0 ; i < n; i ++ ){ move_inside(i); val = press_button(); cand.push_back(i); if(val > 1){ move_outside(i); } else{ in.insert(i); } } for(int i = 1; i < n; i ++ ){ swap(cand[i], cand[gen(i + 1)]); } int dist = in.size(); int l = 1; int r = n/dist + 1; int mid; while(l + 1 < r){ mid = (l + r) / 2; if(mid * dist > n){ r = mid; continue; } for(auto i : cand){ if(!in.count(i)){ move_inside(i); val = press_button(); if(val > mid){ move_outside(i); } else{ in.insert(i); } if(in.size() == mid * dist) break; } } if(in.size() == mid * dist){ l = mid; } else{ r = mid; cand.clear(); for(auto q : in){ move_outside(q); cand.push_back(q); } for(int i = 1; i < cand.size(); i ++ ){ swap(cand[i], cand[gen(i + 1)]); } in.clear(); } } return l; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:56:30: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |                 if(in.size() == mid * dist) break;
      |                    ~~~~~~~~~~^~~~~~~~~~~~~
insects.cpp:59:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if(in.size() == mid * dist){
      |            ~~~~~~~~~~^~~~~~~~~~~~~
insects.cpp:69:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for(int i = 1; i < cand.size(); i ++ ){
      |                            ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...