Submission #1074330

#TimeUsernameProblemLanguageResultExecution timeMemory
1074330c2zi6Rarest Insects (IOI22_insects)C++17
47.50 / 100
172 ms1264 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "insects.h" mt19937 rng; VI rngind; void movein(int i) { move_inside(rngind[i]); } void moveout(int i) { move_outside(rngind[i]); } int n, D; int solution1() { VI vis(n); int ans = 2e9; replr(i, 0, n-1) if (!vis[i]) { vis[i] = true; movein(i); int cnt = 1; replr(j, i+1, n-1) if (!vis[j]) { movein(j); if (press_button() == 2) { vis[j] = true; cnt++; } moveout(j); } setmin(ans, cnt); moveout(i); } return ans; } int solution2() { VI vis(n); int k = -1; int ans = 0; replr(i, 0, n-1) if (!vis[i]) { vis[i] = true; movein(i); VI a; a.pb(i); replr(j, i+1, n-1) if (!vis[j]) { movein(j); if (press_button() == 2) { moveout(j); } else { vis[j] = true; a.pb(j); } } for (int i : a) moveout(i); if (k == -1) { k = a.size(); } else if (a.size() != k) break; ans++; } return ans; } bool check(int k) { // is answer >= k VI a; rep(i, n) { movein(i); if (press_button() > k) moveout(i); else a.pb(i); } bool ret = (a.size() == D * k); for (int i : a) moveout(i); return ret; } int min_cardinality(int N) { rng = mt19937(chrono::steady_clock().now().time_since_epoch().count()); n = N; rngind = VI(n); rep(i, n) rngind[i] = i; /*shuffle(all(rngind), rng);*/ if (true) { movein(0); VI a; a.pb(0); replr(j, 1, n-1) { movein(j); if (press_button() == 2) moveout(j); else a.pb(j); } for (int i : a) moveout(i); D = a.size(); } /*cout << D << endl;*/ /*replr(k, 0, n-1) cout << check(k) << " ";*/ /*cout << endl;*/ int l = 1, r = n+1; while (l + 1 < r) { int m = (l + r) / 2; if (check(m)) l = m; else r = m; } return l; if (D < sqrt(n)) return solution1(); return solution2(); return -1; }

Compilation message (stderr)

insects.cpp: In function 'int solution2()':
insects.cpp:86:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         } else if (a.size() != k) break;
      |                    ~~~~~~~~~^~~~
insects.cpp: In function 'bool check(int)':
insects.cpp:100:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     bool ret = (a.size() == D * k);
      |                 ~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...