| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1250911 | haiphong5g0 | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <bits/stdc++.h>
#define task "TEST"
#define task2 "A"
#define pl pair<ll, ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (int i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (int i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int Mod = 998244353;
const int maxn = 1e3;
const ll Inf = 1e16;
pair<vector<int>, ll> res;
ll P[maxn+1], num[maxn+1], A[maxn+1], n;
deque<pair<vector<int>, ll> > knowledge;
pair<vector<int>, ll> transaction(ll val){
vector<int> a; a.clear();
ll sum = val;
FOR(i, 0, n-1, 1) {
if (sum >= A[i]) {
a.pb(i); sum -= A[i];
}
}
return mp(a, sum);
}
void Sub2_3(ll n) {
FOR(i, 1, n-2, 1) {
res = transaction(P[i-1]-2);
for (auto p : res.fi) num[p]++;
if (res.fi[0] != i) P[i] = P[i-1] - 1;
else P[i] = P[i-1] - 2;
}
FOR(i, 1, n-2, 1) FOR(j, num[i], i-1, 1)
transaction(P[i]);
FOR(j, num[n-1], n-2, 1) transaction(P[n-2]-1);
}
void Fix(pair<vector<int>, ll>& know) {
FOR(i, 0, (ll)know.fi.size()-1, 1) {
ll p = know.fi[i];
if (P[p] == 0) continue;
know.fi.erase(know.fi.begin() + i);
know.se -= P[p]; i--;
}
}
void Add(ll val) {
res = transaction(val);
for (auto p : res.fi) num[p]++;
res.se = val - res.se;
Fix(res); knowledge.pb(res);
}
void Sub6(ll n) {
ll val = P[0] - 1;
while (true) {
Add(val);
if (res.fi.size() == 1) P[res.fi[0]] = res.se;
if (P[n-1] != 0) break;
if (res.fi.size() != 1) val = res.se / res.fi.size();
else val = P[res.fi[0]] - 1;
}
bool ck = 0; ck = 1;
FOR(i, 1, n-1, 1) if (P[i] == 0) ck = 0;
while (!ck) {
FOR(i, 0, (ll)knowledge.size()-1, 1) {
pair<vector<int>, ll> know = knowledge[i];
Fix(know);
if (know.fi.size() == 2) Add(know.se/2);
else if (know.fi.size() == 1) {
ll a = know.fi[0];
P[a] = know.se;
}
if (know.fi.size() <= 1) knowledge.erase(knowledge.begin() + i), i--;
}
ck = 1;
FOR(i, 1, n-1, 1) if (P[i] == 0) ck = 0;
}
FOR(i, 1, n-1, 1) FOR(j, num[i], i-1, 1)
Add(P[i]);
}
// std::pair<std::vector<int>, long long> transaction(long long M)
void buy_souvenirs(int n, long long P0) {
P[0] = P0; Sub6(n);
}