Submission #1063816

#TimeUsernameProblemLanguageResultExecution timeMemory
1063816baldwinhuang1Rarest Insects (IOI22_insects)C++17
47.50 / 100
169 ms1400 KiB
#include <bits/stdc++.h> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); bool check(int N, int mid, int uniqueValues) { int amountInside = 0; // cout << "Mid: " << mid << '\n'; // cout << press_button() << '\n'; vector<int> trackInside; for (int i = 0; i < N; i++) { move_inside(i); amountInside++; trackInside.push_back(i); int curr = press_button(); if (curr > mid) { move_outside(i); amountInside--; trackInside.erase(trackInside.end() - 1); } else if (curr == mid && amountInside == (uniqueValues * mid)) { for (auto &i: trackInside) { move_outside(i); } return true; } } for (auto &i: trackInside) { move_outside(i); } return false; } int min_cardinality(int N) { vector<int> mask(N, false); int uniqueValues = 0; for (int i = 0; i < N; i++) { move_inside(i); if (press_button() == 1) { mask[i] = true; uniqueValues++; continue; } else { move_outside(i); } } for (int i = 0; i < N; i++) { if (mask[i] == true) { move_outside(i); } // cout << mask[i] << ' '; } // cout << check(N, 1024, uniqueValues) << '\n'; // cout << check(N, 511, uniqueValues) << '\n'; // cout << check(N, 255, uniqueValues) << '\n'; // cout << check(N, 127, uniqueValues) << '\n'; // cout << check(N, 63, uniqueValues) << '\n'; // cout << check(N, 31, uniqueValues) << '\n'; // cout << check(N, 15, uniqueValues) << '\n'; // cout << check(N, 7, uniqueValues) << '\n'; // cout << check(N, 3, uniqueValues) << '\n'; // cout << check(N, 1, uniqueValues) << '\n'; // cout << check(N, 2, uniqueValues) << '\n'; // return 0; int high = 2048; // 2^11 int low = 0; int ans = -1; while (low <= high) { int mid = low + (high - low) / 2; // cout << low << ' ' << high << ' ' << mid << '\n'; if (check(N, mid, uniqueValues)) { // cout << "True" << '\n'; low = mid + 1; ans = mid; } else { // cout << "False" << '\n'; high = mid - 1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...