oj.uz

Submission #1062180

# Submission time Handle Problem Language Result Execution time Memory
1062180 2024-08-16T20:38:55 Z jerzyk Rarest Insects (IOI22_insects) C++17
0 / 100
 16 ms 2508 KB 
#include <bits/stdc++.h>
#include "insects.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
bool out[N], czy[N], wh[N];
vector<int> cur;
int lft, dif;
int ansd = 1;

int findDif(int n)
{
    for(int i = 0; i < n; ++i)
    {
        move_inside(i);
        cur.pb(i);
        if(press_button() > 1)
        {
            cur.pop_back();
            move_outside(i);
        }
    }
    int ans = cur.size();
    for(int i = 0; i < (int)cur.size(); ++i)
    {
        out[cur[i]] = true;
        move_outside(cur[i]);
    }
    cur.clear();
    return ans;
}

int Check(int x, int n)
{
    int ans = 0, xd = 0;
    for(int i = 0; i < n; ++i)
    {
        wh[i] = false;
        if(out[i]) continue;
        move_inside(i);
        czy[i] = true;
        ans = press_button();
        ++xd;
        if(ans > x + 1)
        {
            --xd;
            --ans;
            wh[i] = true;
            czy[i] = false;
            move_outside(i);
        }
        if(xd == dif * (x + 1))
            break;
    }
    //int cp = ans;
    //cerr << "xddd " << x << " " << " " << xd << " " << ans << " " << lft << "\n";
    if(xd == dif * (x + 1))
    {
        ans = x + 1;
        ansd += x + 1;
    }
    else
        ans = min(ans, x);
    for(int i = 0; i < n; ++i)
    {
        if(out[i]) continue;
        if(!czy[i]) continue;
        if(xd == dif * (x + 1))
            wh[i] = true;
        move_outside(i);
        czy[i] = false;
        /*if(xd != dif * (x + 1) && press_button() < cp)
        {
            czy[i] = true;
            move_inside(i);
            wh[i] = true;
        }*/
    }
    /*for(int i = 0; i < n; ++i)
    {
        if(out[i]) continue;
        if(!czy[i]) continue;
        move_outside(i);
    }*/
    //if(xd == dif * (x + 1))
        //return ans;


    for(int i = 0; i < n; ++i)
        if(wh[i])
        {
            --lft;
            out[i] = true;
        }
    return min(ans, x);
}

int BS(int maks, int n)
{
    int p = 0, k = maks;
    while(p < k)
    {
        int s = (p + k) / 2;
        if(dif == 1)
            return lft;
        int x = Check(s, n);
        if(x > s)
            p = s + 1;
        else
            k = s;
        k = min(k, lft);
    }
    return p;
}

int min_cardinality(int n)
{
    dif = findDif(n);
    lft = n - dif;
    //cerr << "dif " << dif << "\n";
    int m = lft / dif;
    int ans = BS(m, n) + ansd;
    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 2 ms 2504 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Incorrect 2 ms 2392 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 2 ms 2504 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Incorrect 2 ms 2392 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 9 ms 2496 KB Output is correct
8 Correct 8 ms 2508 KB Output is correct
9 Incorrect 16 ms 2392 KB Wrong answer.
10 Halted 0 ms 0 KB -