Cod sursa(job #2836997)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 21 ianuarie 2022 13:44:54
Problema Schi Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

//ifstream cin("schi.in");
//ofstream cout("schi.out");

int n, aib[30001], v[30001], rez[30001];

void update(int pos, int val)
{
    for(int i=pos; i<=n; i += (i&(-i)))
        aib[i] += val;
}

int query(int pos)
{
    int sum = 0;
    for(int i=pos; i>0; i -= (i&(-i)))
        sum += aib[i];
    return sum;
}

int cb(int i)
{
    int pos = 0;
    int pas = 1<<17;
    int rez = 2e9;
    while(pas)
    {
        if(pos + pas <= n)
        {
            if(pos + pas <= n && pos+pas <= v[i] + query(pos + pas))
            {
                if(pos+pas == v[i] + query(pos + pas))
                    rez = min(pos + pas, rez);
                else
                    pos += pas;
            }
        }
        pas >>= 1;
    }
    return rez;
}

int main()
{
    FILE *fin, *fout;
    fin = fopen( "schi.in", "r" );
    fscanf( fin, "%d", &n );
    for(int i=1; i<=n; i++)
    {
        fscanf( fin, "%d", &v[i] );
    }
    fclose( fin );
    for(int i=n; i>0; i--)
    {
        int curent = query(v[i]);
        int pos = v[i] + curent;
        int next = query(pos);
        while(curent < next)
        {
            curent = next;
            pos = v[i] + curent;
            next = query(pos);
        }
        rez[pos]=i;
        update(pos, 1);
    }
    fout = fopen( "schi.out", "w" );
    for(int i = 1; i <= n; i++ )
        fprintf( fout, "%d\n", rez[i] );
    return 0;
}