Cod sursa(job #2230386)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 9 august 2018 22:12:05
Problema Order Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 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) {
		if (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;
	if (n == 1)
		fout << 1;
	if (n == 2)
		fout << 2 << " " << 1;
	if (n >= 3) {
		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;
}