Submission #1274006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274006		feining_for_gm	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 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;

//void __print(int x) {std::cerr << x;}
//void __print(long x) {std::cerr << x;}
//void __print(long long x) {std::cerr << x;}
//void __print(unsigned x) {std::cerr << x;}
//void __print(unsigned long x) {std::cerr << x;}
//void __print(unsigned long long x) {std::cerr << x;}
//void __print(float x) {std::cerr << x;}
//void __print(double x) {std::cerr << x;}
//void __print(long double x) {std::cerr << x;}
//void __print(char x) {std::cerr << '\'' << x << '\'';}
//void __print(const char *x) {std::cerr << '\"' << x << '\"';}
//void __print(const std::string &x) {std::cerr << '\"' << x << '\"';}
//void __print(bool x) {std::cerr << (x ? "true" : "false");}
//template<typename T, typename V>
//void __print(const std::pair<T, V> &x) {std::cerr << '{'; __print(x.first); std::cerr << ','; __print(x.second); std::cerr << '}';}
//template<typename T>
//void __print(const T &x) {int f = 0; std::cerr << '{'; for(auto &i: x) std::cerr << (f++? "," : ""), __print(i); std::cerr << "}";}
//void _print() {std::cerr << "]\n";}
//template <typename T, typename... V>
//void _print(T t, V... v) {__print(t); if(sizeof...(v)) std::cerr << ", "; _print(v...);}
//#ifndef ONlINE_JUDGE
//#define debug(x...) std::cerr << "[" << #x << "] = ["; _print(x)
//#else
//#define debug(x...)
//#endif
//
//int totelements;
//std::vector<long long> r;
//
//std::pair<std::vector<int>, long long> transaction(long long m) {
//    std::vector<int> res;
//    for(int i = 0; i < totelements; i++) {
//        if(r[i] <= m) {
//            res.push_back(i);
//            m -= r[i];
//        }
//    }
//    return {res, m};
//}

int n;
std::map<long long, std::pair<std::vector<int>, long long>> trans;
std::vector<long long> costs;
std::vector<int> counts;

void recurse(std::vector<int> elements, long long sum) {
//    debug(elements);
//    debug(costs);
//    debug(counts);
    std::set<int> need;
    for(auto e : elements) need.insert(e);

    while(!need.empty()) {
        int denom = (int)elements.size();
        if(denom == 1) {
            if(elements[0] == n-1) costs[n-1] = sum;
            else {
                long long prev = sum;
                if(!costs[elements[0]]) {
                    if(costs[elements[0]+1]) {
                        costs[elements[0]] = sum;
                        return;
                    }
                    if(trans.find(prev-1) == trans.end()) {
                        trans[prev-1] = transaction(prev-1);
//                        debug(trans[prev-1].first);
                        trans[prev-1].second = prev-1-trans[prev-1].second;
                        for(auto q : trans[prev-1].first) ++counts[q];
                    }
                    std::pair<std::vector<int>, long long> temp = trans[prev-1];
                    std::pair<std::vector<int>, long long> res;
                    res.second = temp.second;
                    for(auto q : temp.first) {
                        if(costs[q]) res.second -= costs[q];
                        else res.first.push_back(q);
                    }

                    if(res.first.empty()) {
                        costs[elements[0]] = sum;
                        return;
                    }

                    recurse(res.first, res.second);
                    costs[elements[0]] = sum;
                }
            }
            return;
        } else {
            long long query = sum/denom;
            if(trans.find(query) == trans.end()) {
                trans[query] = transaction(query);
//                debug(trans[query].first);
                trans[query].second = query-trans[query].second;
                for(auto q : trans[query].first) ++counts[q];
            }
            std::pair<std::vector<int>, long long> temp = trans[query];
            std::pair<std::vector<int>, long long> res;
            //RE, figure out why INF looping
            res.second = temp.second;
            for(auto q : temp.first) {
                if(costs[q]) res.second -= costs[q];
                else res.first.push_back(q);
            }

            if(res.first.empty()) return;

            recurse(res.first, res.second);
            for(auto i : elements) {
                if(costs[i]) need.erase(i);
            }

            std::vector<int> etemp;
            for(auto e : elements) {
                if(costs[e]) sum -= costs[e];
                else etemp.push_back(e);
            }

            elements = etemp;

            if(elements.size() == 1) {
                if(elements[0] != n-1 && !costs[elements[0]+1]) continue;
                else costs[elements[0]] = sum;
                return;
            }
        }
    }

//    debug(costs);
}

void buy_souvenirs(int N, long long p0) {
    n = N;
    costs.resize(n, 0);
    counts.resize(n, 0);
    costs[0] = p0;
    std::set<int> need;
    for(int i = 1; i < n; ++i) need.insert(i);

    while(!need.empty()) {
        int prev = *need.begin()-1;
        if(trans.find(costs[prev]-1) == trans.end()) {
            trans[costs[prev]-1] = transaction(costs[prev]-1);
//            debug(trans[costs[prev]-1].first);
            trans[costs[prev]-1].second = costs[prev]-1-trans[costs[prev]-1].second;
            for(auto q : trans[costs[prev]-1].first) ++counts[q];
        }
        std::pair<std::vector<int>, long long> temp = trans[costs[prev]-1];
        std::pair<std::vector<int>, long long> res;
        res.second = temp.second;
        for(auto q : temp.first) {
            if(costs[q]) res.second -= costs[q];
            else res.first.push_back(q);
        }

        recurse(res.first, res.second);
        for(int i = 1; i < n; ++i) {
            if(costs[i]) need.erase(i);
        }
    }

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

//    debug(costs);
//    debug(counts);
}

//int main() {
//    std::cin >> totelements;
//    r.resize(totelements);
//    for(int i = 0; i < totelements; i++) std::cin >> r[i];
//    buy_souvenirs(totelements, r[0]);
//}

• 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