Cod sursa(job #2783331)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 14 octombrie 2021 11:38:30
Problema Schi Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359d
#define ll long long
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?a:b)
#define bmax(a,b)((a>b)?a:b)
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
ll n,m=1,t,a[962145],b[962145][2],c[30001],d[30001],i,j,k,x,y,r,l,e,f,o;bool q;
void ff(long long i){
if(o>=b[i][0]&&i<=k)
    {if(o>=b[i][1])
        r+=a[i];
        else ff(i*2),ff(i*2+1);}
}
int main()
{
in>>n;
while(m<n)m*=2,++l;
k=m*2-1;
for(i=0;i<n;i++)in>>c[i],b[m+i][0]=b[m+i][1]=i+1,a[m+i]=1;
while(i<=k)b[m+i][0]=b[m+i][1]=i+1,i++;
for(i=m-1;i;i--)a[i]=a[i*2]+a[i*2+1],b[i][0]=b[i*2][0],b[i][1]=b[i*2+1][1];
i=n;
while(i>0)
{
    --i;
    e=1,f=n;
    while(e!=f)
    {
        o=(e+f)/2;
        r=0;ff(1);
        //cout<<o<<' '<<r<<'\n';
        if(r<c[i])e=o+1;else f=o;
    }
    //cout<<e<<'\n';
    d[e]=i+1;
    j=m+e-1;
    while(j)a[j]--,j/=2;
}
for(i=1;i<=n;i++)out<<d[i]<<'\n';
}