제출 #1274135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274135		flowyeyedod	선물 (IOI25_souvenirs)	C++17	0 / 100	14 ms	344 KiB

souvenirs

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

// This is the interactive function provided by the grader
pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    vector<int> P(N, 0);   // store prices
    P[0] = P0;

    // Step 1: Deduce all prices P[1..N-1]
    // Since all prices are ≤ 10, we can try M = 1..P0-1
    for (int m = 1; m < P0; ++m) {
        auto res = transaction(m);
        auto &types = res.first;
        long long rem = res.second;

        // Deduce price for the first souvenir we get
        for (int t : types) {
            if (t != 0 && P[t] == 0) { // ignore type 0
                P[t] = m - rem;
            }
        }
    }

    // Fill any missing prices (should be ≤ 10)
    for (int i = 1; i < N; ++i) {
        if (P[i] == 0) P[i] = 1; // minimal value if not discovered
    }

    // Step 2: Buy exactly i souvenirs of type i
    // Simple: repeat transaction(P[i]) exactly i times
    for (int i = 1; i < N; ++i) {
        for (int cnt = 0; cnt < i; ++cnt) {
            transaction(P[i]);
        }
    }
}

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