Submission #1319358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319358		Trisanu_Das	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	12 ms	400 KiB

souvenirs

#include <bits/stdc++.h>
using namespace std;

pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    int vars = N - 1; 
    vector<vector<long long>> A;
    vector<long long> B;
    vector<long long> got(N, 0);

    long long step = max(1LL, P0 / (2 * N + 5));
    long long M = P0 - 1;

    while ((int)A.size() < vars && M >= 0) {
        auto res = transaction(M);
        auto &L = res.first;
        long long R = res.second;

        vector<long long> row(vars, 0);

        for (int t : L) {
            got[t]++;
            if (t > 0)
                row[t - 1] = 1;
        }

        long long paid = M - R;

        A.push_back(row);
        B.push_back(paid);

        M -= step;
    }

    int eq = A.size();

    vector<long long> P(vars, 0);

    int r = 0;
    for (int c = 0; c < vars && r < eq; ++c) {
        int piv = -1;
        for (int i = r; i < eq; ++i) {
            if (A[i][c] != 0) {
                piv = i;
                break;
            }
        }
        if (piv == -1) continue;

        swap(A[r], A[piv]);
        swap(B[r], B[piv]);

        for (int i = 0; i < eq; ++i) {
            if (i == r) continue;
            if (A[i][c] == 0) continue;

            long long factor = A[i][c];
            for (int j = c; j < vars; ++j)
                A[i][j] -= factor * A[r][j];

            B[i] -= factor * B[r];
        }
        r++;
    }

    for (int i = vars - 1; i >= 0; --i) {
        int pivot_col = -1;
        for (int j = 0; j < vars; ++j)
            if (A[i][j] != 0) {
                pivot_col = j;
                break;
            }
        if (pivot_col == -1) continue;

        long long sum = B[i];
        for (int j = pivot_col + 1; j < vars; ++j)
            sum -= A[i][j] * P[j];

        P[pivot_col] = sum / A[i][pivot_col];
    }

    for (int i = 1; i < N; ++i) {
        long long need = i - got[i];
        while (need > 0) {
            transaction(P[i - 1]);
            need--;
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33