Submission #1263664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263664		gotkako	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

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

bool test = false;

void buy_souvenirs(int N, long long P0) {
    vector<long long> P(N),C(N);
    P.at(0) = P0;
    long long check = P0-1;
    vector<bool> already(N); already.at(1) = true;
    vector<pair<vector<int>,long long>> result;
    while(true){
        if(test) cout << check << endl;
        pair<vector<int>,long long> buy = transaction(check);
        auto &[B,coin] = buy;
        if(test){
            cout << "buy:";
            for(auto b : B) cout << b << " ";
            cout << " " << coin << endl;
        }
        coin = check-coin;
        for(auto pos : B) C.at(pos)++;
        
        int siz = B.size();
        vector<bool> del(siz);
        for(int i=0; i<siz; i++) if(P.at(B.at(i)) != 0) coin -= P.at(B.at(i)),del.at(i) = true;
        {
            vector<int> B2;
            for(int i=0; i<siz; i++) if(!del.at(i)) B2.push_back(B.at(i));
            siz = B2.size(); swap(B,B2);
        }
        assert(siz > 0);
        if(siz == 1){
            P.at(B.at(0)) = coin;
            while(true){
                vector<int> era;
                for(int i=0; i<(int)result.size(); i++){
                    auto &[B2,left] = result.at(i);
                    for(int k=B2.size(); k--;) if(P.at(B2.at(k)) != 0){
                        left -= P.at(B2.at(k));
                        B2.erase(B2.begin()+k);
                    }             
                    if(B2.size() == 1){
                        P.at(B2.at(0)) = left;
                        era.push_back(i);
                    }
                    else if(B2.size() == 0) era.push_back(i);
                }
                if(era.size() == 0) break;
                reverse(era.begin(),era.end());
                for(auto pos : era) result.erase(result.begin()+pos);
            }
         
            check = 0;
            if(test){for(int i=0; i<N; i++) cout << P.at(i) << " "; cout << endl;}
            if(test){for(int i=0; i<N; i++) cout << C.at(i) << " "; cout << endl;}
            
            for(int i=N-1; i>0; i--) if(P.at(i) == 0 && P.at(i-1) != 0 && !already.at(i)){
                already.at(i) = true;
                check = P.at(i-1)-1;
                break;
            }
            if(check == 0){
                for(auto [C,left] : result){
                    int minc = *min_element(C.begin(),C.end());
                    int maxc = *max_element(C.begin(),C.end());
                    int n = C.size();
                    bool ng = false;
                    for(int i=minc; i<=maxc; i++) if(P.at(i) != 0){ng = true; break;}
                    
                    if(ng) continue;
                    check = left/n;
                }
                if(result.size() == 0) break;
            }
            assert(check != 0);
        }
        else{
            check = coin/siz;
            result.emplace_back(buy);
        }    
    }
    for(int i=0; i<N; i++) while(C.at(i) < i){
        if(test) cout << P.at(i) << endl;
        transaction(P.at(i)),C.at(i)++; 
    }
}

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