Cod sursa(job #1304490)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 28 decembrie 2014 22:48:23
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#include<fstream>
#include<string>

using namespace std;

#define dbg(x) (cout<<#x<<" = "<<(x)<<'\n')
#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "schi";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

const int NMAX = 30000 + 5;

#define DIM 300000
char buff[DIM];
int poz = 0;

void read(int &numar) {
    numar = 0;

    while (buff[poz] < '0' || buff[poz] > '9')
        if (++poz == DIM)
            fread(buff, 1, DIM, stdin), poz = 0;

    while ('0' <= buff[poz] && buff[poz] <= '9') {
        numar = numar * 10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff, 1, DIM, stdin), poz = 0;
    }
}

int N;
int V[NMAX];
int AIB[NMAX];
int sol[NMAX];

inline void update(int i) {
    for(; i <= N; i += i & (-i))
        AIB[i]++;
}

inline int query(int i) {
    int ans = 0;
    for(; i; i -= i & (-i))
        ans += AIB[i];
    return ans;
}

int main() {
    int i, lo, mi, hi, p;

#ifndef ONLINE_JUDGE
    ifstream fin(inputFile);
    ofstream fout(outputFile);
#endif

    fin >> N;

    for(i = 1; i <= N; i++)
        fin >> V[i];

    for(i = N; i >= 1; i--)
        for(lo = V[i], hi = V[i] + query(N); lo <= hi; ) {
            mi = (lo + hi) / 2;

            p = query(mi) + V[i];

            if(mi == p && !sol[mi]) {
                update(mi);
                sol[mi] = i;
                break;
            } else if(mi < p)
                lo = mi + 1;
            else
                hi = mi - 1;
        }

    for(i = 1; i <= N; i++)
        fout << sol[i] << '\n';

    return 0;
}