Submission #628865

#TimeUsernameProblemLanguageResultExecution timeMemory
628865welleythRarest Insects (IOI22_insects)C++17
Compilation error
0 ms0 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int CNTQ[3] = {}; int getQ(){ return max(CNTQ[0],max(CNTQ[1],CNTQ[2])); } int min_cardinality(int N) { // for(int i = 0; i < 50; i++){ // cout << i+1 << " " << i+1 << " "; // } // cout << "\n"; // return 0; int col[N]; for(int i = 0; i < N; i++) col[i] = 0; int c = 0; int mn = N; int pos[N+1]; bool was[N]; int pref[N+1]; for(int i = 0; i <= N; i++) pos[i] = -1; for(int i = 0; i < N; i++) was[i] = false; for(int i = 0; i < N; i++) pref[i] = -1; bool in[N]; vector<int> order; for(int i = 0; i < N; i++){ move_inside(i); if(press_button() == 1){ was[i] = 1; pref[i] = order.size(); order.push_back(i); } else { if(i) pref[i] = pref[i-1] move_outside(i); } } sort(order.begin(),order.end()); c = order.size(); for(int i = 0; i < order.size(); i++){ col[order[i]] = i; pos[col[order[i]]] = order[i]; in[i] = 1; } if(2*c > N){ return 1; } // cerr << "ok\n"; // for(int i = 0; i < c; i++){ // cerr << "pos[i] = " << pos[i] << "\n"; // } for(int bt = 0; (1 << bt) < c; bt++){ for(int i = 0; i < c; i++){ if(pos[i] == -1) continue; if(i >> bt & 1 && !in[i]){ in[i] = 1; move_inside(pos[i]); } if((i >> bt & 1) == 0 && in[i]){ move_outside(pos[i]); in[i] = 0; } } for(int i = 0; i < N; i++){ if(was[i] || pref[i] < (1 << bt)) continue; move_inside(i); int szIn = press_button(); assert(szIn < 3); if(szIn == 2){ col[i] |= (1 << bt); } move_outside(i); } map<int,int> cnt; for(int i = 0; i < N; i++){ if(col[i] >= (1 << bt)) continue; cnt[col[i]]++; } // cerr << "col: "; // for(int i = 0; i < N; i++){ // cerr << col[i] << " "; // } // cerr << "\n"; for(auto&[x,y] : cnt) mn = min(mn,y); if(mn == 1) return 1; } map<int,int> cnt; for(int i = 0; i < N; i++){ cnt[col[i]]++; } for(auto&[x,y] : cnt) mn = min(mn,y); return mn; } /** 6 5 8 9 5 9 9 1 2 3 0 0 0 40 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 100 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 10 1 0 2 0 3 0 4 0 5 0 1 1 **/

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:36:36: error: expected ';' before 'move_outside'
   36 |                 pref[i] = pref[i-1]
      |                                    ^
      |                                    ;
   37 |             move_outside(i);
      |             ~~~~~~~~~~~~            
insects.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < order.size(); i++){
      |                    ~~^~~~~~~~~~~~~~