제출 #972683

#제출 시각아이디문제언어결과실행 시간메모리
972683ALeonidou드문 곤충 (IOI22_insects)C++17
49.97 / 100
80 ms1704 KiB
#include "insects.h" #include <variant> #include <vector> #include <iostream> #include <algorithm> #include <set> using namespace std; #define ll int #define F first #define S second #define pb push_back #define sz(x) (ll)x.size() #define endl "\n" typedef vector <ll> vi; typedef pair <ll, ll> ii; typedef vector <ii> vii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } #define MID ((l+r)/2) // void solve(vi &u, ll l, ll r, vi test_subjects, vi &id){ // if (l == r){ // for (ll i =0; i<sz(test_subjects); i++){ // id[test_subjects[i]] = u[l]; // } // } // else{ // vi remaining_test_subjects, opposite_remaining_test_subjects; // //go left: // for (ll i =MID+1; i<r; i++){ // move_outside(u[i]); // } // for (ll i = 0; i<sz(test_subjects); i++){ // move_inside(test_subjects[i]); // ll x = press_button(); // if (x == 2){ // remaining_test_subjects.pb(test_subjects[i]); // } // else{ // opposite_remaining_test_subjects.pb(test_subjects[i]); // } // move_outside(test_subjects[i]); // } // solve(u, l, MID, remaining_test_subjects, id); // for (ll i =MID+1; i<r; i++){ // move_inside(u[i]); // } // //go right: // for (ll i =l; i<=MID; i++){ // move_outside(u[i]); // } // solve(u, MID+1, r, opposite_remaining_test_subjects, id); // for (ll i =l; i<=MID; i++){ // move_inside(u[i]); // } // } // } void tabb(ll n){ for (ll i =0; i<n; i++) cout<<"\t"; } void solve(vi &u, ll l, ll r, vi test_subjects, vi &id, ll tab = 0){ // tabb(tab); // cout<<"l:"<<l<<" r:"<<r<<" test_subjects:"; // printVct(test_subjects); if (!sz(test_subjects)) return; if (l == r){ for (ll i =0; i<sz(test_subjects); i++){ id[test_subjects[i]] = u[l]; } } else{ vi remaining_test_subjects, opposite_remaining_test_subjects; //go left: remaining_test_subjects.clear(); for (ll i =MID+1; i<=r; i++){ move_outside(u[i]); } for (ll i = 0; i<sz(test_subjects); i++){ move_inside(test_subjects[i]); ll x = press_button(); if (x == 2){ remaining_test_subjects.pb(test_subjects[i]); } else{ opposite_remaining_test_subjects.pb(test_subjects[i]); } move_outside(test_subjects[i]); } solve(u, l, MID, remaining_test_subjects, id, tab+1); for (ll i =MID+1; i<=r; i++){ move_inside(u[i]); } //go right: for (ll i =l; i<=MID; i++){ move_outside(u[i]); } solve(u, MID+1, r, opposite_remaining_test_subjects, id, tab+1); for (ll i =l; i<=MID; i++){ move_inside(u[i]); } } } int min_cardinality(int N){ ll n = N; vi v(n); //step 1: make list of unique elements vi u(1,0); move_inside(0); for (ll i =1; i<n;i++){ move_inside(i); ll x = press_button(); if (x == 2){ move_outside(i); } else{ u.pb(i); } } // printVct(u); //step 2: binary search set <ll> st; for (ll i =0; i<sz(u); i++){ st.insert(u[i]); } vi test_subjects, id(n); for (ll i =0; i<n; i++){ if (st.find(i) == st.end()){ test_subjects.pb(i); id[i] = -1; } else{ id[i] = i; } } solve(u, 0, sz(u)-1, test_subjects, id); // printVct(id); sort(id.begin(), id.end()); vi f(n,0); for (ll i =0; i<n; i++){ f[id[i]]++; } ll ans = 1000000000; for (ll i =0; i<n; i++){ if (f[i]){ ans = min(ans, f[i]); } } return ans; } /* 6 5 8 9 5 9 9 5 1 2 2 3 4 10 1 2 2 6 1 3 3 2 6 1 60 1 2 2 6 1 3 3 2 6 1 1 2 2 6 1 3 3 2 6 1 1 2 2 6 1 3 3 2 8 6 1 1 2 2 6 1 3 3 9 6 1 1 15 2 6 1 3 3 2 6 1 1 2 2 6 1 3 3 2 6 1 6 1 2 3 4 5 6 1 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...