Cod sursa(job #809972)

Utilizator DraStiKDragos Oprica DraStiK Data 9 noiembrie 2012 13:45:09
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;

const int SQRT=180;
const int NMAX=30005;

int N, nrBucket, sizeBucket;
int V[NMAX],ret[NMAX],value[NMAX],bucket[SQRT];

void update(int poz) {
	value[poz]=0;
	for (int i=(poz-1)/sizeBucket+1; i<=nrBucket; ++i)
		bucket[i]--;
}

int query(int target) {
	for (int i=1; i<=nrBucket; ++i) {
		if (bucket[i]>=target) {
			int start=(i-1)*sizeBucket;
			for (int sum=0, j=start+1; j<=start+sizeBucket; ++j) {
				if (value[j]!=0 && (++sum)+bucket[i-1]==target)
					return j;
			}
		}
	}

	return -1;
}

int main () {
	freopen ("schi.in","r",stdin);
	freopen ("schi.out","w",stdout);
	cin>>N;
	sizeBucket = static_cast<int>(sqrt(N));
	nrBucket = N / sizeBucket;

	for (int i = 1; i <= N; ++i)
		cin>>V[i];
	for (int i = 1; i <= N; ++i)
		value[i]=1;
	for (int i=1; i<=nrBucket; ++i)
		bucket[i]=bucket[i-1]+sizeBucket;
	if (N%sizeBucket!=0)
		bucket[++nrBucket]=bucket[nrBucket-1]+N%sizeBucket;

	for (int i=N; i>=1; --i) {
		int poz=query(V[i]);
		update(poz);
		ret[poz]=i;
	}

	for (int i=1; i<=N; ++i)
		cout<<ret[i]<<"\n";
	return 0;
}