Submission #1285768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285768		eri16	선물 (IOI25_souvenirs)	C++20	100 / 100	13 ms	404 KiB

souvenirs

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

using namespace std;

long long n;
long long cnt[101];
long long cost[101];

void Solve(long long money){
	pair<vector<int>, long long> vp1;
	
	vp1= transaction(money);
	
	for (int i=0; i<vp1.first.size(); i++){
	    cnt[vp1.first[i]]++;
	}

	while(vp1.first.size()>1){
		if(cost[vp1.first.back()]!=-1){
			vp1.second+=cost[vp1.first.back()];
			vp1.first.pop_back();
		}
		else{
			Solve((money-vp1.second)/vp1.first.size());
		}
	}
	
	cost[vp1.first[0]]=money-vp1.second;
	if(vp1.first[0]!=n-1 && cost[vp1.first[0]+1]==-1){
		Solve(cost[vp1.first[0]]-1);
	}
}


pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    n=N;
    pair<vector<int>, long long> vp;

    if (n==2){
        transaction(P0-1);
    }
    else if (n==3){
        vp=transaction(P0-1);

        if (vp.first.size()==1){
         
            long long tt=vp.second;
            
            long long p2=P0-1-tt;
            
            transaction(p2-1);            
            
            transaction(p2-1);            
        }
        
        else{
            
            long long tt=vp.second;
            
            long long p2=(P0-1-tt)/2;
            
            transaction(p2);            
        }
    }
    /*
    else{
        long long sm=n-2;
        
        for (int i=1; i<n; i++){

            long long cnt=i-1;
            
            if (i==n-1){
                cnt=sm;
            }
            
            vp=transaction(P0-1);
            
            long long tt=vp.second;            
                
            if (vp.first.size()==2){sm--;tt++;}
            
            long long pk=P0-1-tt;
                
            P0=pk;
                
            for (int j=0; j<cnt; j++){
                transaction(pk);    
            }
        }
    }
    */
    else{
	memset(cnt,0,sizeof(cnt));
	memset(cost,-1,sizeof(cost));
	
	cost[0]=P0;
	
	Solve(P0-1);
	
	for(int i=1; i<n; i++){
		for(int j=i; j>cnt[i]; j--){
			transaction(cost[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