| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1064217 | MarwenElarbi | Thousands Islands (IOI22_islands) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=2005;
int sz[nax];
vector<int> insects;
vector<int> to_do[nax];
int ls=0;
int rs=-1;
int c=0;
void daq(int l,int r){
if(l==r){
sz[l]+=to_do[l].size();
return;
}
int mid=(r+l)/2;
while(ls<l){
c--;
move_outside(insects[ls++]);
}
while(ls>l){
c++;
move_inside(insects[--ls]);
}
while(rs<mid){
c++;
move_inside(insects[++rs]);
}
while(rs>mid){
c--;
move_outside(insects[rs--]);
}
vector<int> left,right;
for(auto u:to_do[mid]){
move_inside(u);
int a=press_button();
if(a==2) left.pb(u);
else right.pb(u);
move_outside(u);
}
to_do[(mid+l)/2]=left;
to_do[(mid+1+r)/2]=right;
if(to_do[(mid+l)/2].size()) daq(l,mid);
if(to_do[(mid+1+r)/2].size()) daq(mid+1,r);
return;
}
int min_cardinality(int N){
int n=N;
move_inside(0);
insects.pb(0);
int cnt=1;
vector<int> cur;
for (int i = 1; i < n; ++i)
{
move_inside(i);
cnt++;
int a=press_button();
if(a==2){
if(cnt<=2) sz[0]++;
else{
cur.pb(i);
}
move_outside(i);
cnt--;
}else{
insects.pb(i);
}
}
for(auto u:cur) to_do[(insects.size()-1)/2].pb(u);
for (int i = 0; i < insects.size(); ++i)
{
move_outside(insects[i]);
}
daq(0,insects.size()-1);
int mn=1e9;
for (int i = 0; i < insects.size(); ++i)
{
mn=min(mn,sz[i]);
}
return mn+1;
}