Cod sursa(job #1253304)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 1 noiembrie 2014 02:27:51
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

int n, j, sum;
vector<int> v, a, q;

void UPDATE(int poz, int val);
int SUM(int poz);

int main()
{
    is >> n;
    v.resize(n + 1);
    a.resize(n + 1);
    q.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> v[i];
        UPDATE(i, 1);
    }
    for ( int i = n; i; --i )
    {
        j = 0;
        for ( int p = 1 << 14; p; p >>= 1 )
            if ( j + p <= n )
            {
                sum = SUM(j + p);
                //os << j + p << " " << sum << "\n";
                if ( sum <= v[i] )
                {
                    j += p;
                    if ( sum == v[i] && !q[j] )
                    {
                        p = 1;
                        q[j] = i;
                        UPDATE(j, -1);
                    }
                    else
                        if ( sum == v[i] )
                        {
                            while ( q[j] )
                                --j;
                            p = 1;
                            q[j] = i;
                            UPDATE(j, -1);
                        }
                }
            }
        /*for ( int i = 1; i <= n; ++i )
            os << q[i] << " ";
        os << "\n";*/
    }
    for ( int i = 1; i <= n; ++i )
        os << q[i] << "\n";
    is.close();
    os.close();
    return 0;
}

void UPDATE(int poz, int val)
{
    for ( int i = poz; i <= n; i += i & -i )
        a[i] += val;
}

int SUM(int poz)
{
    int s = 0;
    for ( int i = poz; i; i -= i & -i )
        s += a[i];
    return s;
}