| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 212969 | Nucleist | The Big Prize (IOI17_prize) | C++14 | 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.
int kal;
dos aski[200001];
map<ve,set<int>>yo;
map<int,ve>gg;
int ans=0;
bool vis[200001];
set<int>curi;
set<dos>koli;
int rod=0,belek=-1;
int find_best(int n)
{
int county=0;
rod=0;belek=n-1;
for (int i = 0; i < min(n,470); ++i)
{
ve sal=ask(i);
county++;
int yol=sal[0]+sal[1];
if(yol==0)return i;
kal=max(kal,yol);
}
queue<pair<int,dos>>q;
int low=470;
int high=n-1;
ve last=ask(n-1);
county++;
if(last[0]+last[1]==0)return n-1;
int med=(low+high)/2;
q.push({med,{low,high}});
while(!q.empty())
{
//debug(county)
auto u=q.front();
q.pop();
int index=u.first;
int indexa=index;
int l=u.second.first;
int r=u.second.second;
bool ki=true;
for(auto it:koli)
{
if(l>=it.first && r<=it.second)
{
ki=false;break;
}
}
if(ki)
{
if(vis[index] || (l>belek || r<rod))continue;
vis[index]=1;
ve k = ask(index);
ve kaka=k;
county++;
while(k[0]+k[1]!=kal && index<r)
{
if(k[0]==0 && k[1]==0){
debug(county)
return index;
}
else
{
if(k[0]+k[1]==1)
{
if(k[0]==1){belek=min(belek,index-1);}
else rod=max(rod,index+1);
}
//if(index==3273)debug(1)
for(auto it:gg)
{
if(it.first<index)
{
ve cur;
cur.resize(2);
cur=it.second;
//if(index==3273)debugs(2,it.first);
if(yo.find(it.second)!=yo.end())yo[it.second].erase(it.first);
//if(index==3273)debugs(2,it.first);
///if(index==3273)debug(cur[1])
cur[1]--;
//if(index==3273)debugs(2,it.first);
yo[cur].insert(it.first);
//if(index==3273)debugs(2,it.first);
}
}
//if(index==3273)debug(1)
curi.insert(index);
}
index++;
if(!vis[index]){k=ask(index);vis[index]=1;county++;}
else k=gg[index];
}
//if(index==3273)debug(1)
vis[index]=1;
int indexi=0,indexi1=0;
for(auto it:curi)
{
if(it<index)indexi++;
else indexi1++;
}
k[0]-=indexi;
k[1]-=indexi1;
gg[index]=k;
yo[k].insert(index);
bool ka=true,ka1=true;
if(yo.find(k)!=yo.end())
{
auto u=(*(yo[k].begin()));
if(u>index){
ka1=false;
koli.insert({index,u});}
if(u<index)
{
ka=false;
koli.insert({u,index});
}
}
if(index==3273)debug(1)
//if(index!=indexa)ka=true;
/*while(kaka[0]+kaka[1]!=kal && indexa>l)
{
if(kaka[0]==0 && kaka[1]==0){
debug(county);return indexa;
}
else
{
if(kaka[0]+kaka[1]==1)
{
if(kaka[0]==1){belek=min(belek,indexa-1);}
else rod=max(rod,indexa+1);
}
for(auto it:gg)
{
if(it.first<indexa)
{
auto cur=it.second;
yo[it.second].erase(it.first);
it.second[1]--;
yo[it.second].insert(it.first);
}
}
curi.insert(indexa);
}
indexa--;
if(!vis[indexa]){kaka=ask(indexa);vis[indexa]=1;county++;}
else kaka=gg[indexa];
}
vis[indexa]=1;
indexi=0,indexi1=0;
for(auto it:curi)
{
if(it<indexa)indexi++;
else indexi1++;
}
kaka[0]-=indexi;
kaka[1]-=indexi1;
gg[indexa]=kaka;
yo[kaka].insert(indexa);
if(yo.find(kaka)!=yo.end())
{
auto u=(*(yo[kaka].begin()));
if(u<indexa)ka=false;
}*/
if(!vis[(l+indexa)/2])q.push({(l+indexa)/2,{l,indexa}});
if(ka1 && !vis[(index+r)/2])q.push({(index+r)/2,{index,r}});
}}
//debug(county)
return 0;
}