Submission #845826

#	Time	Username	Problem	Language	Result	Execution time	Memory
845826		Marco_Escandon	Rarest Insects (IOI22_insects)	C++17	57.14 / 100	89 ms	1400 KiB

insects

#include<bits/stdc++.h>
using namespace std;
#include <vector>
typedef long long ll;


void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int n)
{
    ll bs=1000000000000;
    ll k=0;set<ll> s;
    for(int i=0; i<n; i++)
    {
        move_inside(i);
        if(press_button()==2)
            move_outside(i);
        else
            s.insert(i);
    }
    k=s.size();
    for(auto i: s)move_outside(i);s.clear();
    if(n*log2(n/k)>n*k/2)
    {
        ll v[n]={ };
        for(int i=0; i<n; i++)
        {
            if(v[i]==0)
            {
                move_inside(i);
                for(int j=i+1; j<n; j++)
                {
                    if(v[j]==0)
                    {
                        move_inside(j);
                        if(press_button()==2)
                        {
                            v[i]++;
                            v[j]=-1;
                        }
                        move_outside(j);
                    }

                }
                move_outside(i);
            }
        }
        for(int j=0; j<n; j++)
        {
            if(v[j]!=-1)
                bs=min(bs,v[j]+1);
        }
        return bs;
    }
    ll a=1,b=(n/k)+1;
    while(abs(a-b)!=1)
    {
        ll m=(a+b)/2;
        ll c=0;
        for(int i=0; i<n; i++)
        {
            move_inside(i);
            if(press_button()==m+1)
            {
                move_outside(i);
                c++;
            }
            else
            {
                s.insert(i);
            }
        }
        for(auto i: s)move_outside(i);s.clear();
        if(m*k+c!=n)
            b=m;
        else a=m;
    }
    return b-1;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:23:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |     for(auto i: s)move_outside(i);s.clear();
      |     ^~~
insects.cpp:23:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |     for(auto i: s)move_outside(i);s.clear();
      |                                   ^
insects.cpp:74:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |         for(auto i: s)move_outside(i);s.clear();
      |         ^~~
insects.cpp:74:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |         for(auto i: s)move_outside(i);s.clear();
      |                                       ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 32.14 / 75