Submission #1318258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318258		1ota	선물 (IOI25_souvenirs)	C++20	3 / 100	12 ms	400 KiB

souvenirs

#include <bits/stdc++.h>
#ifdef EVAL
#include "souvenirs.h"
#endif
using namespace std;

#define endl "\n"
#define int long long
#define int32 int32_t
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

#ifndef EVAL
vector<int> TheP, TheC;
pair<vector<int32>, int> transaction (int m){
    vector<int32> cur;
    for (int i = 0; i < (int) TheP.size(); i++){
        if (TheP[i] <= m) cur.push_back(i), m -= TheP[i], TheC[i]++;
    } return pair<vector<int32>, int>{cur, m};
}
#endif

void buy_souvenirs (int32 N, int p0){
    int n = N, cur = 1, c = 0, fg = -1;
    vector<int> cnt(n, 0), a(n, p0);

    auto query = [&](int m){
        if (c >= 5000) return pair<vector<int32>, int>{vector<int32>{0}, m};
        c++; return transaction(m);
    };

    for (;; cur <<= 1){
        auto [chosen, m] = query(cur);
        if (m != cur) { fg = chosen[0]; a[fg] = cur - m; cnt[fg]++; break; }
    }

    for (int i = fg-1; i > 0; i--){
        int p = a[i+1] + 1;
        auto [chosen, m] = query(p);
        if (m == 1) cnt[i+1]++, a[i] = p + 1;
        else { 
            if ((int) chosen.size() == 1) cnt[i]++, a[i] = p; 
            else cnt[fg]++, cnt[i+1]++, a[i] = p + 1;
        }
    }

    for (int i = fg+1; i < n; i++){
        int p = a[i-1] - 1;
        auto [chosen, m] = query(p);
        cnt[i]++; a[i] = p - m;
    }

    for (int i = 0; i < n; i++) for (; cnt[i] < i; cnt[i]++) transaction(a[i]);
}

#ifndef EVAL
int32 main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(entire(a)); reverse(entire(a));
    TheP = a; TheC.resize(n, 0); buy_souvenirs(n, a[0]);

    bool isgood = true;
    for (int i = 0; i < n; i++){
        if (TheC[i] != i) isgood = false;
    }

    if (isgood) cout << "OK" << endl;
    else cout << "FUCK" << endl;
    return 0;
}
#endif

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