Submission #1259794

#TimeUsernameProblemLanguageResultExecution timeMemory
1259794ro9669Souvenirs (IOI25_souvenirs)C++20
39 / 100
12 ms412 KiB
#include "souvenirs.h" #include <bits/stdc++.h> #define fi first #define se second #define sz(a) int(a.size()) #define all(a) a.begin(),a.end() using namespace std; typedef long long ll; typedef pair<vector<int> , long long> vll; const int maxN = 107; const int maxM = 5007; // int n; // ll p[maxN]; // pair<vector<int> , ll> transaction(ll m){ // // cout << "start : " << m << "\n"; // vector<int> tmp; // for (int i = 0 ; i < n ; i++){ // if (m >= p[i]){ // m -= p[i]; // tmp.push_back(i); // } // } // // for (int x : tmp) cout << x << " "; // // cout << "\n"; // // cout << m << "\n"; // // cout << "-------------------------\n"; // return {tmp , m}; // } ll f(ll x){ return (1ll * x * (x + 1)) / 2; } ll P[maxN]; int cnt[maxN]; vector<vll> T; void transformer(vll &X){ vector<int> tmp; for (int id : X.fi){ if (P[id] == 0){ tmp.push_back(id); } else{ X.se -= P[id]; } } X.fi = tmp; } void buy_souvenirs(int n , ll p0){ int total = 0; set<ll> A , B; P[0] = p0; total++; A.insert(P[0] - 1); while (total < n){ while (total < n && sz(A) > 0){ ll val = *prev(A.end()); A.erase(prev(A.end())); B.insert(val); vll X = transaction(val); for (int id : X.fi) cnt[id]++; X.se = val - X.se; transformer(X); if (sz(X.fi) == 0) break; T.push_back(X); if (sz(X.fi) == 1){ int pos = X.fi[0]; P[pos] = X.se; total++; if (B.count(P[pos] - 1) == 0) A.insert(P[pos] - 1); break; } else{ val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1; if (B.count(val) == 0) A.insert(val); } } for (int i = sz(T) - 1 ; i >= 0 ; i--){ transformer(T[i]); vll X = T[i]; if (sz(X.fi) == 0) continue; if (sz(X.fi) == 1){ int pos = X.fi[0]; P[pos] = X.se; total++; } ll val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1; if (B.count(val) == 0) A.insert(val); } } for (int i = 0 ; i < n ; i++){ for (int j = 0 ; j < i - cnt[i] ; j++) transaction(P[i]); } // cout << "---------\n"; // cout << total << "\n"; // for (int i = 0 ; i < n ; i++) cout << (cnt[i] <= i) << " "; // cout << "\n"; // for (int i = 0 ; i < n ; i++) cout << P[i] << " "; } // int main(){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("templete.inp" , "r" , stdin); // cin >> n; // for (int i = 0 ; i < n ; i++) cin >> p[i]; // buy_souvenirs(n , p[0]); // return 0; // }
#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...