Submission #1318262

#TimeUsernameProblemLanguageResultExecution timeMemory
13182621otaSouvenirs (IOI25_souvenirs)C++20
18 / 100
1 ms400 KiB
#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){
    auto [chosen, m] = transaction(p0 - 1); 
    m = p0 - 1 - m;
    if ((int) chosen.size() == 1){
        transaction(m - 1); transaction(m - 1);
    } else {
        transaction(m / 2);
    }
    // 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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...