제출 #1302437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302437		regulardude6	선물 (IOI25_souvenirs)	C++20	0 / 100	1072 ms	332 KiB

souvenirs

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

static pair<int,long long> sim(const vector<int>& P, long long M){
    long long r=M;
    int mask=0;
    for(int i=0;i<(int)P.size();i++){
        if(r>=P[i]){
            r-=P[i];
            mask|=(1<<i);
        }
    }
    return {mask,r};
}

void buy_souvenirs(int N, long long P0){
    vector<vector<int>> cand;
    vector<int> vals;
    for(int x=1;x<=10;x++) if(x<P0) vals.push_back(x);

    vector<int> cur(N);
    cur[0]=(int)P0;

    function<void(int,int,int,vector<int>&)> dfs = [&](int idx,int last,int need,vector<int>& pick){
        if((int)pick.size()==need){
            vector<int> P(N);
            P[0]=(int)P0;
            for(int i=1;i<N;i++) P[i]=pick[i-1];
            cand.push_back(P);
            return;
        }
        for(int v=last-1;v>=1;v--){
            bool ok=true;
            for(int x:pick) if(x==v) ok=false;
            if(!ok) continue;
            if(v>=P0) continue;
            pick.push_back(v);
            dfs(idx+1,v,need,pick);
            pick.pop_back();
        }
    };

    if(N==1) return;
    vector<int> pick;
    dfs(1,(int)P0,N-1,pick);

    auto bestM = [&](int lb)->long long{
        long long best=-1;
        int bestWorst=INT_MAX;
        for(int m=lb;m<=P0-1;m++){
            unordered_map<long long,int> cnt;
            cnt.reserve(cand.size()*2+7);
            for(auto &P:cand){
                auto s=sim(P,m);
                long long key=((long long)s.first<<20) ^ (s.second&((1LL<<20)-1));
                cnt[key]++;
            }
            int worst=0;
            for(auto &kv:cnt) worst=max(worst,kv.second);
            if(worst<bestWorst){
                bestWorst=worst;
                best=m;
            }
        }
        if(best==-1) best=lb;
        return best;
    };

    while(cand.size()>1){
        int lb=1;
        for(auto &P:cand) lb=max(lb,P.back());
        long long m=bestM(lb);
        auto real=transaction(m);
        int mask=0;
        for(int t:real.first) mask|=(1<<t);
        long long rem=real.second;

        vector<vector<int>> nxt;
        nxt.reserve(cand.size());
        for(auto &P:cand){
            auto s=sim(P,m);
            if(s.first==mask && s.second==rem) nxt.push_back(P);
        }
        cand.swap(nxt);
    }

    vector<int> P=cand[0];
    for(int i=1;i<N;i++){
        for(int t=0;t<i;t++){
            transaction(P[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