제출 #1312130

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

souvenirs

#include <bits/stdc++.h>
using namespace std;
//#define int long long

vector<int>a;
int n;
pair<vector<int>,int>transaction(int num){
    vector<int>ans;
    int og = num;
    for(int i=0;i<n;i++){
        if(num>=a[i]){
            ans.push_back(i);
            num-=a[i];
        }
    }//cout << " " << ans.size() << "::";
    //for(auto it : ans)cout << it << " ";
    //cout << "-- " << num << endl;
    if(ans.empty()){
        cout << og << "  BAAAAAD - none " << num << endl;
        //_sleep(100);
    }
    return {ans,num};
}
//pair<vector<int>,long long>transaction(long long cost);
void to_buy(int ind,long long cost,vector<long long>&vals,vector<int>&cant){
    if(vals[ind]!=-1)return;
    //cout << ind << "?";
    pair<vector<int>,long long>ans = transaction(cost);
    for(auto it : ans.first)cant[it]++;
    if(ans.first.empty()){
        //cout << vals.size() <<" "<< vals[n-1] <<" " << ind << "- error- " << cost << endl;
        //_sleep(100);
        return;
    }
    if(ans.first.size()==1){
        vals[ans.first[0]]=cost-ans.second;
        //cout << "VALS::" <<ans.first[0] << " " << cost-ans.second << endl;
        if(ans.first[0]<ind)to_buy(ind,vals[ans.first[0]]-1,vals,cant);
    }else{
        int bef_ind = ind;
        ind = ans.first[0];
        reverse(ans.first.begin(),ans.first.end());
        long long nxt = ans.second;
        long long act_cant = ans.first.size();
        for(auto it : ans.first){
            if(it==ind)continue;
            if(vals[it]==-1){
                long long act_cost = (cost-nxt+act_cant-1)/act_cant-(act_cant)/2;
                //cout << ind << " " << cost << "-->" << it << " " << act_cost << endl;
                to_buy(it,act_cost,vals,cant);
            }
            nxt+=vals[it];
            act_cant--;
        }vals[ind]=cost-nxt;
        //cout << "VALS2::" << ind << " -- " << cost-nxt << '\n';
        if(vals[bef_ind]==-1){
            int best_aprox = 0;
            while(bef_ind>=0){
                if(vals[bef_ind]!=-1){
                    best_aprox = vals[bef_ind];
                    break;
                }bef_ind--;
            }to_buy(bef_ind,best_aprox-1,vals,cant);
        }
    }return;
}
int done = 0;
void buy_souvenirs(int N, long long P0){
    vector<long long>vals(N,-1);
    vector<int>cant(N,0);
    vals[0]=P0;
    for(int i=1;i<N;i++){
        if(vals[i]==-1){
            to_buy(i,vals[i-1]-1,vals,cant);
        }
    }
    for(int i=0;i<N;i++){
        if(cant[i]>i)cout << "BBBBAAAAAAAAD" << "- big"<<i  << endl;
        else{
            //if(vals[i]!=a[i])cout << "BAD-error" << endl;
            while(cant[i]<i){
                transaction(vals[i]);
                cant[i]++;
            }
        } 
    }done++;
    return;
}
/*
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    int MAXI = 10;
    while(t--){
        n = 3;
        //cout << n << '\n';
        a.resize(n);
        for(int i=0;i<n;i++){
            a[i] = rand()%MAXI;
        }
        sort(a.begin(),a.end());
        auto it = unique(a.begin(),a.end());
        int x = 0;
        while(it!=a.end()){
            (*it) = MAXI+x;
            x++;
            it++;
        }
        sort(a.begin(),a.end(),greater<int>());
        //for(int i=0;i<n;i++)cout << a[i] << " ";
        //cout << '\n';
        buy_souvenirs(n,a[0]);

        a.clear();
    }cout << done << endl;
    return 0;
}*/

• 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