Cod sursa(job #2489277)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 noiembrie 2019 11:59:27
Problema Schi Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <string.h>
#define NMAX 30005
#define ub(x) (x & -x)
#include <stdio.h>
#include <ctype.h>

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

using namespace std;

ofstream fout("schi.out");

int aib[NMAX], clas[NMAX], v[NMAX], n;

void update(int p, int val)
{
    for (int i = p; i <= n; i += ub(i))
        aib[i] += val;
}

int query(int p)
{
    int suma = 0;
    for (int i = p; i >= 1; i -= ub(i))
        suma += aib[i];
    return suma;
}

int bsearch(int p, int u, int key)
{
    int m;

    while (p <= u)
    {
        m = (p + u) / 2;
        if(query(m) <= key) p = m + 1;
        else u = m - 1;
    }

    m = (p + u) / 2;

    if (query(m) > key) m--;
    while (query(m) == key && m) m--;

    m++;

    if (query(m) == key) return m;
    return -1;
}


int main()
{
    InParser fin("schi.in");

    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        update(i, 1);
    }

    for (int i = n; i >= 1; --i)
    {
        int p = bsearch(v[i], n, v[i]);
        clas[p] = i;
        update(p, -1);
    }

    for (int i = 1; i <= n; ++i)
        fout << clas[i] << "\n";

    return 0;
}