제출 #830891

#제출 시각아이디문제언어결과실행 시간메모리
830891caganyanmaz드문 곤충 (IOI22_insects)C++17
53.16 / 100
180 ms432 KiB
#include <bits/stdc++.h> #include "insects.h" #define pb push_back using namespace std; #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif int n; set<int> basis; set<int> addition; set<int> machine; bool check(int val) { for (int i = 0; i < n; i++) { if (machine.find(i) != machine.end()) continue; move_inside(i); addition.insert(i); if (press_button() > val) { move_outside(i); addition.erase(i); } } bool res = ( machine.size() + addition.size() ) == val * basis.size(); if (res) for (int i : addition) machine.insert(i); else for (int i : addition) move_outside(i); addition.clear(); return res; } int test_a() { int l = 1, r = 1 + (n / basis.size()); debug(l, r); while (r - l > 1) { int m = l+r>>1; debug(m); if (check(m)) l = m; else r = m; } debug(l); return l; } vector<int> bs; int get_min(int l, int r, vector<int>& v) { if (r - l == 1) { debug(l, v); return v.size()+1; } int m = l+r>>1; for (int i = l; i < m; i++) { if (machine.find(bs[i]) != machine.end()) continue; machine.insert(bs[i]); move_inside(bs[i]); } for (int i = m; i < r; i++) { if (machine.find(bs[i]) == machine.end()) continue; machine.erase(bs[i]); move_outside(bs[i]); } vector<int> lv, rv; for (int i : v) { move_inside(i); if (press_button() > 1) lv.pb(i); else rv.pb(i); move_outside(i); } int lres = get_min(l, m, lv); int rres = get_min(m, r, rv); return min(lres, rres); } int test_b() { vector<int> v; for (int i = 0; i < n; i++) if (basis.find(i) == basis.end()) v.pb(i); return get_min(0, bs.size(), v); } int min_cardinality(int N) { n = N; for (int i = 0; i < n; i++) { move_inside(i); if (press_button() > 1) move_outside(i); else basis.insert(i); } for (int i : basis) { bs.pb(i); machine.insert(i); } return test_a(); /* if (basis.size() > BLOCK) return test_a(); else return test_b(); */ }

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

insects.cpp: In function 'int test_a()':
insects.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int m = l+r>>1;
      |           ~^~
insects.cpp: In function 'int get_min(int, int, std::vector<int>&)':
insects.cpp:68:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int m = l+r>>1;
      |          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...