Cod sursa(job #1077518)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 11 ianuarie 2014 14:00:32
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 0.71 kb
#include <fstream>
using namespace std;

int main() {
	int N, K;
	ifstream in("farfurii.in");
	in >> N >> K;
	in.close();

	int *v = new int[N + 1], i = 1;

	while ((N - i) * (N - i + 1) / 2 >= K) {
		v[i] = i;
		++i;
	}
	--i;

	int val = N, pos = i;
	while (i <= N) {
		v[i++] = val--;
	}

	int inversiuni = (N - pos) * (N - pos + 1) / 2;
	while (inversiuni > K) {
		//schimb numarul de pe pos cu primul numar mai mic ca el
		for (int j = pos + 1; j <= N; ++j) {
			if (v[j] < v[pos]) {
				swap(v[j], v[pos]);
				break;
			}
		}
		--inversiuni;
	}

	ofstream out("farfurii.out");
	for (int i = 1; i <= N; ++i) {
		out << v[i] << " ";
	}
	out.close();

	delete[] v;
	return 0;
}