Cod sursa(job #2432261)

Utilizator capmareAlexCapmare Alex capmareAlex Data 22 iunie 2019 18:49:12
Problema Order Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 30005
ifstream fin("order.in");
ofstream fout("order.out");
int n;
int aint[NMAX*4];
int copii;
int query( int nod, int st , int dr, int l, int r)
{
    if(st >= l && dr <= r)return aint[nod];
    int mid = ( st + dr )/2;
    int ans = 0;
    if( mid >=l)
        ans= query(nod * 2, st, mid, l , r);
    if(mid + 1 <= r)
        ans += query ( nod*2 + 1, mid + 1,dr, l, r);
    return ans;

}
void update( int nod , int st, int dr, int pos, int val)
{
    if(st==dr)aint[nod]+=val;
    else
    {
        int mid = (st+ dr)/2;
        if(mid >= pos)
        {
            update( nod * 2, st, mid, pos, val);
        }
        else update(nod * 2 +1, mid +1, dr, pos, val);
        aint[nod]= aint[nod*2]+ aint[nod*2+1];
    }
}
int main()
{
    fin>>n;
    copii = n;
    int poz=1;
    //cout << query(1, 1, n, 1, 2) << "\n";
    for(int i = 1;i <= n; ++i)
       {
        int st, dr;
        int j = i;
        if( j > copii)
        {
            j %= copii;
            if(j == 0 )j = copii;
        }
        int ans;
        int stn = poz- query(1,1,n,1, poz);
        //cout << "poz: " << poz << " " << stn << "\n";
        if(copii-stn<j)
        {
            int x= j-copii+stn;
            int mid;
            st = 1;
            dr = poz-1;
            for(mid = (st + dr)/2; st<=dr; mid= (st+dr)/2)
            {
                if(mid-query(1,1,n,1, mid)>=x)
                {
                    ans=mid;
                    dr=mid-1;
                }
                else st=mid+1;
            }
        }
        else
        {
        //cout << "\n" << i << " " << poz << " " << stn << "\n";
          int x= j;
          int mid;
          st = poz+1;
          dr = n;
             for(mid = (st + dr)/2; st<=dr; mid= (st+dr)/2)
            {
                if(mid-query(1,1,n,1, mid)-stn >=x)
                {
                    ans=mid;
                    dr=mid-1;
                }
                else st=mid+1;
            }
        }
        update(1,1,n,ans,1);
        poz = ans;
        fout<<ans<<" ";
        --copii;
    }
    return 0;
}