oj.uz

Submission #936722

# Submission time Handle Problem Language Result Execution time Memory
936722 2024-03-02T15:32:54 Z GrindMachine Rarest Insects (IOI22_insects) C++17
0 / 100
 67 ms 684 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*
 
refs:
https://youtu.be/mm5Nv81P5u8?t=19948
edi
 
*/
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
#include "insects.h"

int min_cardinality(int n) {
    vector<int> uniq_guys;

    rep(i,n){
        move_inside(i);
        int res = press_button();
        if(res >= 2){
            move_outside(i);
        }
        else{
            uniq_guys.pb(i);
        }
    }

    trav(i,uniq_guys){
        move_outside(i);
    }
    
    if(sz(uniq_guys) == 1){
        return n;
    }

    if(sz(uniq_guys) == n){
        return 1;
    }

    vector<bool> ignore(n);

    auto ok = [&](int mid){
        // check if ans <= mid
        // check if ans < mid+1

        vector<int> good, bad;
 
        rev(i,n-1,0){
            if(ignore[i]) conts;
            move_inside(i);
            int res = press_button();
            if(res > mid+1){
                bad.pb(i);
                move_outside(i);
            }
            else{
                good.pb(i);
            }
        }
    
        if(sz(good) == sz(uniq_guys)*(mid+1)){
            // everybody occurs at least mid+1 times
            return false;
        }
        else{
            // at least one guy occurs < (mid+1) #of times
            // i.e at least one guys occurs <= mid #of times
            // right endpoint of range decreases
            // so ignore all bad guys in future iterations
            trav(i,bad){
                ignore[i] = 1;
            }
            
            return true;
        }
    };

    int l = 1, r = n/sz(uniq_guys)-1;
    int ans = n/sz(uniq_guys);
 
    while(l <= r){
        int mid = (l+r) >> 1;
        // is min <= mid?
        if(ok(mid)){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
 
    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Partially correct 3 ms 344 KB Output is partially correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 8 ms 448 KB Output is correct
9 Partially correct 67 ms 684 KB Output is partially correct
10 Partially correct 34 ms 672 KB Output is partially correct
11 Correct 24 ms 600 KB Output is correct
12 Correct 20 ms 600 KB Output is correct
13 Incorrect 27 ms 436 KB Wrong answer.
14 Halted 0 ms 0 KB -