Cod sursa(job #1069320)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 29 decembrie 2013 19:50:06
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cmath>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

#define nmax 30001
#define bucket_dim 180

short i, j, n;
short Ind[nmax];

short pos, cnt, dim, buckets;
deque <short> bucket[bucket_dim];
deque <short> :: iterator it;

int main() {
	fin >> n;
	dim = sqrt(1.0 * n);
	buckets = (n / dim) + 1;
	for (i = 1; i <= n; ++i) {
		fin >> Ind[i], --Ind[i];
		cnt = Ind[i] / dim;
		pos = Ind[i] % dim;
		if (bucket[cnt].size()) {
			it = bucket[cnt].begin() + pos;
			bucket[cnt].insert(it, i);
		}
		else
			bucket[cnt].push_back(i);
		for (j = 0; j < buckets; ++j) {
			if (bucket[j].size() > dim) {
				int x = bucket[j].back();
				bucket[j].pop_back();
				bucket[j + 1].push_front(x);
			}
		}
	}
	for (i = 0; i < buckets; ++i) 
		for (it = bucket[i].begin(); it != bucket[i].end(); ++it) 
			fout << *it << '\n';
	return 0;
}