| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314195 | AhmadAlhussain | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
pair<vector<int>,long long> transaction(long long M);
int cnt=0;
pair<vector<int>,long long>c[105];
int k[105];
long long p1[105];
int let[105];
void remove(vector<int>v) {
for(int i:v) {
let[i]--;
}
}
void buy_souvenirs(int N,long long p0) {
for(int i=0;i<N;i++) {
let[i]=i;
}
long long last=p0-1;
while(true) {
//cout<<last<<' ';
auto [v,r]=transaction(last);
remove(v);
c[v[0]]={v,r};
k[v[0]]=last;
long long sum=last-r;
if(v.size()==1&&v.back()==N-1) {
p1[N-1]=sum;
break;
}
if(v.size()==1) {
last=sum-1;
}
else {
last=sum/long(v.size())-1;
}
}
//cout<<'\n';
for(int i=N-2;i>=2;i--) {
if(c[i].first.empty()) {
//cout<<i<<' '<<2*p1[i+1]<<' ';
auto [v,r]=transaction(2*p1[i+1]);
remove(v);
//cout<<2*p1[i+1]<<' ';
p1[i]=2*p1[i+1]-r;
for(int j=1;j<v.size();j++) {
p1[i]-=p1[v[j]];
}
//cout<<i<<' '<<p1[i]<<'3'<<'\n';;
}
else {
auto [v,r]=c[i];
//cout<<i<<' '<<v.size()<<' '<<r<<' '<<k[i]<<'\n';
p1[i]=k[i]-r;
//cout<<p1[i]<<' ';
for(int j=1;j<v.size();j++) {
//cout<<i<<' ';
p1[i]-=p1[v[j]];
}
//cout<<i<<' '<<p1[i]<<'\n';
//cout<<i<<' '<<p1[i]<<'\n';;
}
}
cout<<'\n';
for(int i=2;i<N;i++) {//cout<<i<<' '<<p1[i]<<'\n';
for(int j=0;j<let[i];j++) {
transaction(p1[i]);
}
}
}
namespace {
const int CALLS_CNT_LIMIT = 10'000;
int calls_cnt;
int N;
std::vector<long long> P;
std::vector<int> Q;
void quit(const char* message) {
printf("%s\n", message);
exit(0);
}
} // namespace
std::pair<std::vector<int>, long long> transaction(long long M) {
calls_cnt++;
if (calls_cnt > CALLS_CNT_LIMIT)
quit("Too many calls");
if (M >= P[0] || M < P[N - 1]) {
//cout<<M<<' ';
quit("Invalid argument");
}
std::vector<int> L;
long long R = M;
for (int i = 0; i < N; i++) {
if (R >= P[i]) {
R -= P[i];
Q[i]++;
L.push_back(i);
}
}
return {L, R};
}
int main() {
assert(1 == scanf("%d", &N));
P.resize(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%lld", &P[i]));
fclose(stdin);
Q.assign(N, 0);
calls_cnt = 0;
buy_souvenirs(N, P[0]);
for (int i = 0; i < N; i++)
printf("%s%d", i ? " " : "", Q[i]);
printf("\n");
fclose(stdout);
return 0;
}