Cod sursa(job #2230379)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 9 august 2018 21:43:23
Problema Order Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#pragma once


#include<fstream>
#include<iostream>

using namespace std;

#define DIM 120000

int lazy[DIM], nrElem, start;
ifstream fin("order.in");
ofstream fout("order.out");

int MIN(int a, int b) {
	if (a > -1 && b > -1) {
		if (a <= b)
			return a;
		return b;
	}
	if (b <= -1) {
		return a;
	}
	if (a <= -1) {
		return b;
	}
}

int MAX(int a, int b) {
	if (a >= b)
		return a;
	return b;
}

class Info {
public:
	int iMin, iMax;
};

Info aint[DIM];

void manageNode(int nod, int st, int dr) {
	if (lazy[nod] != 0) {
		aint[nod].iMax += lazy[nod];
		aint[nod].iMin += lazy[nod];
		if (st != dr) {
			lazy[2 * nod] += lazy[nod];
			lazy[2 * nod + 1] += lazy[nod];
		}
		lazy[nod] = 0; // updated and propagated
	}
}

void constr(int nod, int st, int dr, int poz) {
	if (st == dr) {
		aint[nod].iMax = st-1;
		aint[nod].iMin = st-1;
		return;
	}
	int mid = st + (dr - st) / 2;
	if (poz <= mid)
		constr(2 * nod, st, mid, poz);
	else
		constr(2 * nod + 1, mid + 1, dr, poz);

	aint[nod].iMax = MAX(aint[2 * nod].iMax, aint[2 * nod + 1].iMax);
	aint[nod].iMin = MIN(aint[2 * nod].iMin, aint[2 * nod + 1].iMin);

}

void update(int nod, int st, int dr, int uStart, int uEnd, int diff) {
	manageNode(nod, st, dr);
	if (uStart <= st && uEnd >= dr) {
		aint[nod].iMax += diff;
		aint[nod].iMin += diff;
		if (st != dr) {
			lazy[2 * nod] += diff;
			lazy[2 * nod + 1] += diff;
		}
		return;
	}
	int mid = st + (dr - st) / 2;

	if (uStart <= mid)
		update(2 * nod, st, mid, uStart, uEnd, diff);
	if (uEnd > mid)
		update(2 * nod + 1, mid + 1, dr, uStart, uEnd, diff);

	manageNode(2 * nod, st, mid);
	manageNode(2 * nod + 1, mid + 1, dr);

	aint[nod].iMax = MAX(aint[2 * nod].iMax, aint[2 * nod + 1].iMax);
	aint[nod].iMin = MIN(aint[2 * nod].iMin, aint[2 * nod + 1].iMin);
}

void query(int nod, int st, int dr, int pos) {
	manageNode(nod, st, dr);
	if (st == dr && aint[nod].iMax == pos) {
		start = st;
		fout << st << " ";
		aint[nod].iMax = aint[nod].iMin = -1;
		return;
	}

	int mid = st + (dr - st) / 2;

	manageNode(2 * nod, st, mid);
	manageNode(2 * nod + 1, mid + 1, dr);

	if (aint[nod].iMin != -1) {
		if (aint[2 * nod].iMax >= pos && aint[2 * nod].iMin <= pos)
			query(2 * nod, st, mid, pos);
		if (aint[2 * nod + 1].iMax >= pos && aint[2 * nod + 1].iMin <= pos)
			query(2 * nod + 1, mid + 1, dr, pos);
	}
	else {
		query(2 * nod + 1, mid + 1, dr, pos);
	}

	aint[nod].iMax = MAX(aint[2 * nod].iMax, aint[2 * nod + 1].iMax);
	aint[nod].iMin = MIN(aint[2 * nod].iMin, aint[2 * nod + 1].iMin);
}

int main() {
	int nrElem, k=2, pos=1, n;
	fin >> nrElem;
	n = nrElem;
	for (int i = 1; i <= nrElem; i++) {
		constr(1, 1, nrElem, i);
	}
	query(1, 1, nrElem, pos);
	update(1, 1, nrElem, 3, nrElem, -1);
	n--;
	while (n) {
		pos = (pos + k - 1) % n;
		query(1, 1, nrElem, pos);
		if (pos + 2 <= nrElem)
			update(1, 1, nrElem, start+1, nrElem, -1);
		k++;
		n--;
	}
	return 0;
}