#include <iostream>
#include <vector>
using namespace std;
#define int long long
struct bigint
{
int sign=+1;
vector<int> val;
bigint()
{
}
void set(string inp)
{
val.clear();
sign=1;
int n=inp.size();
for(int i=n-1;i>=0;i--)
{
if(inp[i]=='-')
{
sign=-1;
continue;
}
int cur=0,pw=1;
for(int j=0;j<18 and (i-j)>=0;j++)
{
cur+=(inp[i-j]-'0')*pw;
pw*=10;
}
val.push_back(cur);
i-=17;
}
}
void print()
{
if(sign==-1)cout<<'-';
for(int i=val.size()-1;i>=0;i--)
{
cout<<val[i]<<' ';
}
cout<<endl;
}
};
bigint add(bigint a,bigint b);
bool cmp_abs(bigint a,bigint b) // return 0 if a>b 1 else
{
if(a.val.size()>b.val.size())return 0;
if(a.val.size()<b.val.size())return 1;
for(int i=a.val.size()-1;i>=0;i--)
{
if(a.val[i]!=b.val[i])
{
return (a.val[i]<b.val[i]);
}
}
return 1;
}
const int base=1e18;
bigint sub(bigint a,bigint b)
{
// a-b
if(a.sign!=b.sign)
{
b.sign*=-1;
return add(a,b);
}
// cout<<"Sub ";
// a.print();
// b.print();
bigint res;
if(cmp_abs(a,b))
{
// cout<<"B is bigger then A"<<endl;
swap(a,b);
res.sign=-a.sign;
}
else{
res.sign=a.sign;
}
int na=a.val.size();
int nb=b.val.size();
int cry=0;
for(int i=0;i<na;i++)
{
int cb=a.val[i]-cry;
cry=0;
if(i<nb)cb-=b.val[i];
if(cb<0)
{
cb+=base;
cry=1;
}
res.val.push_back(cb);
}
while(res.val.size()>0 and res.val.back()==0)res.val.pop_back();
if(res.val.size()==0)
{
res.sign=+1;
res.val.push_back(0);
}
return res;
}
bigint add(bigint a,bigint b)
{
if(a.sign==1 and b.sign==1)
{
// we do this
}
else if(a.sign==-1 and b.sign==-1)
{
}
else if(a.sign==-1 and b.sign==1)
{
a.sign=1;
return sub(b,a); // b-a
}
else if(a.sign==1 and b.sign==-1)
{
// cout<<"Case ";
// a.print();
// b.print();
b.sign=1;
return sub(a,b);
}
bigint res;
res.sign=a.sign;
int na=a.val.size();
int nb=b.val.size();
int cry=0;
for(int i=0;i<=max(na,nb);i++)
{
int cb=cry;
if(i<na)cb+=a.val[i];
if(i<nb)cb+=b.val[i];
cry=(cb/base);
cb%=base;
res.val.push_back(cb);
}
while(res.val.size()>0 and res.val.back()==0)res.val.pop_back();
if(res.val.size()==0)
{
res.sign=+1;
res.val.push_back(0);
}
return res;
}
const int N=1e6+10;
bigint qp[N];
bigint mi[N],lzy[N];
int ind[N],n;
void push(int l,int r,int v)
{
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
mi[v]=sub(mi[v],lzy[v]);
if(l!=r)
{
lzy[lc]=add(lzy[lc],lzy[v]);
lzy[rc]=add(lzy[rc],lzy[v]);
}
lzy[v].set("0");
}
void build(int l=1,int r=n,int v=1)
{
lzy[v].set("0");
if(l==r)
{
mi[v]=qp[l];
// cout<<"Qp "<<l<<' ';qp[l].print();
ind[v]=l;
return;
}
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
build(l,m,lc);
build(m+1,r,rc);
mi[v]=mi[lc];
ind[v]=ind[lc];
if(cmp_abs(mi[rc],mi[lc]))
{
mi[v]=mi[rc],ind[v]=ind[rc];
}
// cout<<"At "<<l<<' '<<r<<' '<<v<<endl;
// cout<<"Mi ";mi[v].print();
// cout<<"ind "<<ind[v]<<endl;
}
void update(int ql,int qr,bigint& val,int l=1,int r=n,int v=1)
{
push(l,r,v);
if(qr<l or r<ql)return;
if(ql<=l and r<=qr)
{
lzy[v]=add(lzy[v],val); // we have to sub lzy[v] from the min
push(l,r,v);
return;
}
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
update(ql,qr,val,l,m,lc);
update(ql,qr,val,m+1,r,rc);
mi[v]=mi[lc];
ind[v]=ind[lc];
if(cmp_abs(mi[rc],mi[lc]))
mi[v]=mi[rc],ind[v]=ind[rc];
}
main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
string s;
bigint q[n+1]={};
// cin>>s;
// q[0].set(s);
// q[0].print();
int ans[n+1]={};
bigint val[n+1]={};
q[0].set("0");
bigint one;
one.set("1");
for(int i=1;i<=n;i++)cin>>s,q[i].set(s),val[i]=sub(q[i],q[i-1]),qp[i]=sub(add(add(q[i-1],q[i-1]),one),q[i]);
bigint infy=add(q[n],q[n]);
infy.sign=-1;
build();
for(int j=n;j>=1;j--)
{
int mx=ind[1];
ans[mx]=j;
update(mx,mx,infy); // set to infy
update(mx,n,val[mx]);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
}
Compilation message (stderr)
Main.cpp:209:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
209 | main()
| ^~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
