Submission #1252230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252230		tuannm	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	12 ms	412 KiB

souvenirs

//#define test

#ifndef test
#include "souvenirs.h"
#endif // test

#include<bits/stdc++.h>
using namespace std;
int cntBought[101];


#ifdef test
vector<long long> P = {100, 99, 98, 97, 60, 59, 58, 57, 20, 19, 18, 17, 4, 3, 2, 1};

void quit(const char* message){
    printf("%s\n", message);
    exit(0);
}

const int CALLS_CNT_LIMIT = 10000;
int calls_cnt;

pair<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.back())
        quit("Invalid argument");

    vector<int> ret;

    for(int i = 1; i < P.size(); ++i)
        if(P[i] <= M){
            M -= P[i];
            ret.push_back(i);
            ++cntBought[i];
        }

    return make_pair(ret, M);
}
#endif // test

void buy_souvenirs(int N, long long P0){
    vector<long long> p(N, -1), sumUnknown(N, 0);
    p[0] = P0;
    set<int> s[N];

    while(1){
        bool unknown = false;

        for(int i = N - 1; i >= 0; --i){
            if(p[i] == -1)
                unknown = true;

            if(p[i] != -1 && unknown){
                pair<vector<int>, long long> tmp = transaction(p[i] - 1);
                sumUnknown[i + 1] = p[i] - 1 - tmp.second;

                for(int j : tmp.first){
                    if(p[j] != -1)
                        sumUnknown[i + 1] -= p[j];
                    else
                        s[i + 1].insert(j);
                }

                break;
            }

            if(s[i].size() == 1){
                p[i] = sumUnknown[i];
                s[i].clear();

                for(int j = 0; j < N; ++j){
                    auto pt = s[j].find(i);

                    if(pt != s[j].end()){
                        sumUnknown[j] -= p[i];
                        s[j].erase(pt);
                    }
                }

                break;
            }

            if(s[i].size()){
                long long x = sumUnknown[i] / s[i].size();
                pair<vector<int>, long long> tmp = transaction(x);
                long long sum = x - tmp.second;
                int lgs = N;

                for(int j : tmp.first){
                    if(p[j] != -1)
                        sum -= p[j];
                    else{
                        if(lgs == N)
                            lgs = j, s[lgs].clear();

                        s[lgs].insert(j);
                    }
                }

                sumUnknown[lgs] = sum;
                break;
            }
        }

        if(!unknown)
            break;
    }

    for(int i = 1; i < N; ++i)
        while(cntBought[i] < i)
            transaction(p[i]);
}

#ifdef test
int main(){
    buy_souvenirs(P.size(), P[0]);
}
#endif

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