| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 151456 | babo | Lokahian Relics (FXCUP4_lokahia) | 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>
#define x first
#define y second
using namespace std;
int CollectRelics(int,int);
multiset<pair<int,int> >st,st2,st3;
int FindBase(int N){
int i;
for(i=0;i<N;i++)
{
st.insert(make_pair(1,i));
}
while(st.size()>=2)
{
//printf("sz %d , %d %d %d %d %d\n",st.size(),st.begin()->y,next(st.begin())->y,st.begin()->x,next(st.begin())->x);
//printf(" %d\n",CollectRelics(st.begin()->y,next(st.begin())->y));
if(st.begin()->x==next(st.begin())->x)
{
int temp=st.begin()->y==next(st.begin())->y?st.begin()->y:CollectRelics(st.begin()->y,next(st.begin())->y);
if(temp!=-1)
{
//printf("%d\n",st.size());
st.erase(next(st.begin()));
st.insert(make_pair(st.begin()->x*2,temp));
st.erase(st.begin());
//printf("%d\n",st.size());
}
else
{
st2.insert(*st.begin());
st.erase(st.begin());
st2.insert(*st.begin());
st.erase(st.begin());
}
}
else
{
st3.insert(*st.begin());
st.erase(st.begin());
}
}
int las,ans;
if(st.empty())
{
if(st3.empty())
return -1;
else
{
las=st3.rbegin()->y;
ans=st3.rbegin()->x;
st3.erase(st3.rbegin());
}
}
else
{
las=st.begin()->y;
ans=st.begin()->x;
st.erase(st.begin());
}
for(multiset<pair<int,int> >::iterator it=st2.begin();it!=st2.end();it++)
{
int temp=las==it->y?las:CollectRelics(las,it->y);
if(temp!=-1)
{
las=temp;
ans+=it->x;
}
}
for(multiset<pair<int,int> >::iterator it=st3.begin();it!=st3.end();it++)
{
int temp=las==it->y?las:CollectRelics(las,it->y);
if(temp!=-1)
{
las=temp;
ans+=it->x;
}
}
if(ans>N/2)
return las;
return -1;
}