| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 212966 | 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.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
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;
ve ask(int index)
{
ve yo;
yo.pb(aski[index].first);
yo.pb(aski[index].second);
return yo;
}
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())
{
auto u=q.front();
q.pop();
int index=u.first;
int indexa=index;
// debug(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);
}
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);
}
}
curi.insert(index);
}
index++;
if(!vis[index]){k=ask(index);vis[index]=1;county++;}
else k=gg[index];
}
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(index!=indexa)ka=true;
if(indexa!=index)
{
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)
{
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);
}
}
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;koli.insert({u,indexa});}
}
}
else
{
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(ka && !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;
}
int typi[200001];
int main()
{
flash;
freopen("2-16.out","r",stdin);
int n;
cin>>n;
ve ka;
for (int i = 0; i < n; ++i)
{
int k;
cin>>k;
ka.pb(k);
for(int j=1;j<k;j++)
{
aski[i].first+=typi[j];
}
typi[k]++;
}
int ans=0;
//reverse(ka.begin(),ka.end());
memset(typi,0,sizeof typi);
for (int i = n-1; i >= 0; --i)
{
int k=ka[i];
for(int j=1;j<k;j++)
{
aski[i].second+=typi[j];
}
if(aski[i].second==0 && aski[i].first==0)ans=i;
typi[k]++;
}
debug(ans);
debug(find_best(n));
return 0;
}
//code the AC sol !
// BS/queue/map