Cod sursa(job #1077532)

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

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

	int v[MAXN], i = 1, pos = 0;
	long long sum = 0;

	for (i = 1; i <= N; ++i) {
		sum += i;
		v[i] = i;
		if (sum >= K) {
			break;
		}
	}
	--i; pos = i;

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

	long long inversiuni = 1LL * (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();

	return 0;
}