Submission #1314218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314218		AhmadAlhussain	Souvenirs (IOI25_souvenirs)	C++20	53 / 100	12 ms	400 KiB

souvenirs

#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];
long long 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) {
        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());
        }
    }
    for(int i=N-2;i>=2;i--) {
        vector<int>v;
        long long r;
        long long next;
        if(c[i].first.empty()) {
            pair<vector<int>,long long>e=transaction(2*p1[i+1]);
            v=e.first,r=e.second;
            remove(v);
            next=2*p1[i+1];
        }
        else {
            pair<vector<int>,long long>e=c[i];
            v=e.first,r=e.second;
            next=k[i];
        }
        p1[i]=next-r;
        for(int j=1;j<v.size();j++) {
            p1[i]-=p1[v[j]];
        }
    }
    for(int i=2;i<N;i++) {
        for(int j=0;j<let[i];j++) {
            transaction(p1[i]);
        }
    }
}

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