Submission #1249959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249959		tosivanmak	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	11 ms	416 KiB

souvenirs

#include<bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
#define ll long long

pair<vector<int>,ll> starting[105];
ll sm[105];
ll cnt[105]; ll P[105];
void proc(pair<vector<int>,ll>pre, ll ending){
    while(1){
        ll S=pre.second; S--;
        S/=(ll)pre.first.size();
        if(pre.first[0]==ending)break;
        pre=transaction(S);
        pre.second=S-pre.second;
        for(auto& u: pre.first){
            cnt[u]++;
        }
        starting[pre.first[0]]=pre;
    }
}
void buy_souvenirs(int N, long long P0){
    // std::pair<std::vector<int>, long long> transaction(long long M)
    for(int i=0;i<N+5;i++){
        starting[i].first.clear(); starting[i].second=0; sm[i]=0;
    }
    P[0]=P0;
    ll asked=P0-1;
    pair<vector<int>,ll>req=transaction(P0-1);
    req.second=P0-1-req.second;
    starting[req.first[0]]=req;
    pair<vector<int>,ll>pre=req;
    for(int i=0;i<N+5;i++){
        cnt[i]=0;
    }
    for(auto& u: pre.first){
        cnt[u]++;
    }
    while(1){
        ll S=pre.second; S--;
        S/=(ll)pre.first.size();
        if(pre.first[0]==N-1)break;
        pre=transaction(S);
        pre.second=S-pre.second;
        for(auto& u: pre.first){
            cnt[u]++;
        }
        starting[pre.first[0]]=pre;
    }
    for(int i=N-1;i>=0;i--){
        if(starting[i].first.size()!=0){
            while(starting[i].first.size()>1){
                starting[i].second-=P[starting[i].first.back()];
                starting[i].first.pop_back();
            }
            P[i]=starting[i].second;
        }
        else{
            for(int j=i-1;j>=0;j--){
                if(starting[j].first.size()!=0){
                    proc(starting[j],i); break;
                }
            }
            while(starting[i].first.size()>1){
                starting[i].second-=P[starting[i].first.back()];
                starting[i].first.pop_back();
            }
            P[i]=starting[i].second;
        }
        for(int j=i-1;j>=0;j--){
            if(starting[j].first.size()!=0){
                while(starting[j].first.back()>=i){
                    starting[j].second-=P[starting[j].first.back()];
                    starting[j].first.pop_back();
                }
            }
        }
    }
    for(int i=0;i<N;i++){
        while(cnt[i]!=i){
            transaction(P[i]); cnt[i]++;
        }
    }
    return;
}

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