Cod sursa(job #3134816)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 31 mai 2023 11:20:39
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <math.h>
#include <stdio.h>

#include <vector>

int main() {
    freopen("farfurii.in", "r", stdin);
    freopen("farfurii.out", "w", stdout);

    int N, K;
    scanf("%d %d", &N, &K);

    int param = 8 * K + 1, nums = sqrt(param);
    if (nums * nums != param) {
        nums = nums + 1;
    }
    nums = (nums + 2) >> 1;

    int32_t dif = N - nums;

    std::vector<int> pos;

    for (int n = nums, k = K; k > 0; n--) {
        pos.push_back(k);

        int pred = ((n - 1) * (n - 2)) / 2;

        if (k - pred == n - 1) {
            k = pred;
        } else {
            k = pred - (n - 2) + (k - pred);
        }
    }

    std::vector<int32_t> res;

    res.push_back(1 + dif);
    for (int i = pos.size() - 1, n = 1; i >= 0; i--, n++) {
        if (pos[i] == ((n * (n + 1)) / 2)) {
            res.push_back(n + 1 + dif);
        } else {
            int last = res.back();
            res.pop_back();
            res.push_back(n + 1 + dif);
            res.push_back(last);
        }
    }

    for (int i = N - nums; i >= 1; i--) {
        res.push_back(i);
    }

    for (int i = res.size() - 1; i >= 0; i--) {
        printf("%d ", res[i]);
    }
    printf("\n");

    return 0;
}