Submission #1272097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272097		feining_for_gm	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	1082 ms	400 KiB

souvenirs

#include "souvenirs.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

//std::pair<std::vector<int>, int> transaction(long long m) {
//    return {{0}, 0};
//}

struct eq {
    std::vector<int> s;
    long long sum;

    friend bool operator<(const eq &a, const eq &b) {
        if(a.s[a.s.size()-1] !=  b.s[b.s.size()-1]) return a.s[a.s.size()-1] < b.s[b.s.size()-1];
        else return a.sum < b.sum;
    };
};

void buy_souvenirs(int n, long long p0) {
    //we can start by querying p0-1
    std::vector<long long> ans(n, 0);
    ans[0] = p0;
    std::set<int> need;
    for(int i = 1; i < n; ++i) need.insert(i);

    std::map<int, int> cntans;

    //while there exists unknown element in set
    while(!need.empty()) {
        int fir = *need.begin();
        std::set<eq> eqs;
        std::pair<std::vector<int>, long long> stemp = transaction(ans[fir-1]-1);
        eq eq1 = {stemp.first, ans[fir-1]-1-stemp.second};
        eqs.insert(eq1);

        for(auto it : eq1.s) ++cntans[it];

        //while we can still deduce some element from an initial equation
        while(!eqs.empty()) {
            auto [vals, sum] = *eqs.begin();
            int ck = vals.size();
            long long nxt = sum/ck;

            //consider the next "step"
            std::pair<std::vector<int>, long long> ctemp = transaction(nxt);
            eq eqn = {ctemp.first, nxt-ctemp.second};
            for(auto it : eqn.s) ++cntans[it];
            std::set<int> process;
            if(ctemp.first.size() == 1) {
                //we have found a value and can insert into process
                ans[eqn.s[0]] = eqn.sum;
                process.insert(eqn.s[0]);
                need.erase(eqn.s[0]);
            } else {
                eqs.insert(eqn);
            }

            //keep on deducing values from previously found elements when possible
            while(!process.empty()) {
                std::set<eq> neq;
                int cur = *process.begin();
                auto it = eqs.begin();
                while(it != eqs.end()) {
                    std::vector<int> ns;
                    long long tsum = it->sum;
                    for(auto v : it->s) {
                        if(v != cur) ns.push_back(v);
                        else tsum -= ans[v];
                    }

                    if(ns.size() == 1) {
                        ans[ns[0]] = tsum;
                        process.insert(ns[0]);
                        need.erase(ns[0]);
                    } else {
                        neq.insert({ns, tsum});
                    }
                    ++it;
                }

                eqs = neq;
            }
        }
    }

    for(int i = 1; i < n; ++i) {
        for(int j = cntans[i]; j <= i; ++j) transaction(ans[i]);
    }
}

• 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