Cod sursa(job #1077564)

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

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

    int v[MAXN];
    double p = (sqrt(1 + 8*K) - 1) / 2;
    int pos = p;
    if (p != (long long)p) {
			++pos;
    }
    pos = N - pos;

    if (pos < 0) {
			while (1) {}
    }

    for (int i = 1; i < pos; ++i) {
			v[i] = i;
    }
    int val = N;
    for (int i = pos; i <= N; ++i) {
			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 (pos < 0) {
							while (1) {}
						}
            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;
}