제출 #1258880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258880		Aviansh	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

void buy_souvenirs(int n, long long P0) {
    long long val[n];
    fill(val,val+n,-1);
    val[0]=P0;
    set<int>dep[n];
    long long sum[n];
    int cnt[n];
    fill(cnt,cnt+n,0);
    while(1){
        int temp = 0;
        for(int i = 0;i<n;i++){
            if(val[i]==-1){
                temp++;
            }
        }
        if(temp==0){
            break;
        }
        bool req = 0;
        for(int i = n-1;i>=0;i--){
            if(val[i]==-1&&dep[i].size()==0){
                req=1;
            }
            if(val[i]!=-1&&req){
                req=0;
                pair<vector<int>,long long>p = transaction(val[i]-1);
                for(int i : p.first){
                    cnt[i]++;
                }
                long long sm = val[i]-1-p.second;
                set<int>s;
                for(int i : p.first){
                    s.insert(i);
                }
                for(int i : p.first){
                    if(val[i]!=-1){
                        sm-=val[i];
                        s.erase(i);
                    }
                }
                dep[i+1]=s;
                sum[i+1]=sm;
                break;
            }
            if(dep[i].size()==1){
                dep[i].clear();
                val[i]=sum[i];
                break;
            }
            if(dep[i].size()){
                set<int>er;
                for(int x : dep[i]){
                    if(val[x]!=-1){
                        sum[i]-=val[x];
                        er.insert(x);
                    }
                }
                for(int x : er){
                    dep[i].erase(x);
                }
                if(dep[i].size()==1){
                    dep[i].clear();
                    val[i]=sum[i];
                    break;
                }
                pair<vector<int>,long long>p = transaction(sum[i]/dep[i].size());
                for(int i : p.first){
                    cnt[i]++;
                }
                long long sm = sum[i]/dep[i].size()-p.second;
                set<int>s;
                for(int i : p.first){
                    s.insert(i);
                }
                for(int i : p.first){
                    if(val[i]!=-1){
                        sm-=val[i];
                        s.erase(i);
                    }
                }
                dep[*s.begin()]=s;
                sum[*s.begin()]=sm;
                break;
            }
        }
    }
    for(int i = 0;i<n;i++){
        while(cnt[i]<i){
            transaction(val[i]);
            cnt[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