제출 #628596

#제출 시각아이디문제언어결과실행 시간메모리
628596Sorting드문 곤충 (IOI22_insects)C++17
87.59 / 100
123 ms336 KiB
#include "insects.h" #include <vector> #include <random> #include <algorithm> #include <set> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); const int C = 4; int min_cardinality(int n) { vector<int> v; v.push_back(0); move_inside(0); for(int i = 1; i < n; ++i){ move_inside(i); if(press_button() == 2){ move_outside(i); } else v.push_back(i); } for(int x: v) move_outside(x); vector<int> type(n); int k = v.size(); if(k <= C){ vector<bool> in_v(n, false); for(int x: v) in_v[x] = true; for(int i = 0; (1 << i) < k; ++i){ for(int j = 0; j < k; ++j){ if((j >> i) & 1){ type[v[j]] += (1 << i); move_inside(v[j]); } } for(int j = 0; j < n; ++j){ if(in_v[j]) continue; move_inside(j); if(press_button() == 2) type[j] += (1 << i); move_outside(j); } for(int j = 0; j < k; ++j){ if((j >> i) & 1){ move_outside(v[j]); } } } vector<int> cnt(k); for(int i = 0; i < n; ++i) cnt[type[i]]++; return *min_element(cnt.begin(), cnt.end()); } vector<int> rem; for(int i = 0; i < n; ++i){ if(find(v.begin(), v.end(), i) == v.end()) rem.push_back(i); } mt19937 mt(5); int ans = 1; while(!rem.empty()){ // if(rem.size() < k) // return ans; v.clear(); shuffle(rem.begin(), rem.end(), mt); move_inside(rem[0]); v.push_back(rem[0]); for(int i = 1; i < rem.size(); ++i){ int x = rem[i]; move_inside(x); if(press_button() == 1){ v.push_back(x); if(v.size() == k) break; } else{ move_outside(x); } } for(int x: v) move_outside(x); if(v.size() < k) return ans; ++ans; vector<int> rem2; set<int> s; for(int x: v) s.insert(x); for(int x: rem) if(!s.count(x)) rem2.push_back(x); swap(rem, rem2); } return ans; }

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 1; i < rem.size(); ++i){
      |                        ~~^~~~~~~~~~~~
insects.cpp:88:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |                 if(v.size() == k)
      |                    ~~~~~~~~~^~~~
insects.cpp:97:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         if(v.size() < k)
      |            ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...