| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 627505 | inwbear | Digital Circuit (IOI22_circuit) | 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 "insects.h"
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
int cc[2005],re,sq,rr;
pair<int,int>pos[2005];
bool ins[2005];
int min_cardinality(int N) {
re=N;
vector<int>v;
vector<pair<int,int> >fr;
for(int i=0;i<N;i++){
move_inside(i);
if(press_button()>1){
move_outside(i);
fr.pb({i,false});
}
else v.pb(i),ins[i]=true;
}
if(v.size()!=(int)sqrt(v.size())*(int)sqrt(v.size()))sq=(int)sqrt(v.size())+1;
else sq=(int)sqrt(v.size());
for(int i=0;i<v.size();i++)move_outside(v[i]);
for(int i=sq;i<v.size();i+=sq){
rr=0;
for(int j=i;j<v.size()&&j<i+sq;j++){
rr++;
move_inside(v[j]);
}
for(int j=0;j<fr.size();j++){
if(fr[j].S)continue;
move_inside(fr[j].F);
if(press_button()>1){
fr[j].S=true;
rr--;
pos[fr[j].F].F=i/sq;
}
move_outside(fr[j].F);
}
for(int j=i;j<v.size()&&j<i+sq;j++){
move_outside(v[j]);
}
if(rr>0)return 1;
}
for(int j=0;j<fr.size();j++)fr[j].S=true;
for(int i=1;i<sq;i++){
rr=0;
for(int j=i;j<v.size();j+=sq){
move_inside(v[j]);
rr++;
}
for(int j=0;j<fr.size();j++){
if(!fr[j].S)continue;
move_inside(fr[j].F);
if(press_button()>1){
fr[j].S=false;
pos[fr[j].F].S=i;
rr--;
}
move_outside(fr[j].F);
}
for(int j=i;j<v.size();j+=sq){
move_inside(v[j]);
}
if(rr>0)return 1;
}
//for(int i=0;i<v.size();i++)printf("{%d}",v[i]);
//for(int i=0;i<fr.size();i++)printf("[%d %d]",pos[fr[i].F].F,pos[fr[i].F].S);
for(int i=0;i<fr.size();i++){
cc[v[(pos[fr[i].F].F*sq)+pos[fr[i].F].S]]++;
}
for(int i=0;i<v.size();i++)re=min(re,cc[v[i]]+1);
return re;
}