Submission #1249578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249578		PCTprobability	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
ll p[101];
ll cnt[101];
void buy_souvenirs(int N, long long P0) {
  int n=N;
  p[0]=P0;
  auto solve = [&](ll x,auto self) -> void {
    /*cout<<"X"<<" "<<x<<endl;
    for(int i=0;i<n;i++) cout<<p[i]<<" ";
    cout<<endl;*/
    for(int i=n-1;i>=0;i--){
      if(p[i]==0) break;
      if(p[i]>=x) return;
    }
    for(int i=0;i+1<n;i++){
      if(p[i]>=x&&p[i+1]<x&&p[i+1]!=0){
        ll j=i+1;
        while(p[j]!=0&&j<n) j++;
        if(j==n) return;
        x=p[j];
        break;
      }
    }
    //cout<<"Y"<<" "<<x<<endl;
    //for(int i=0;i<n;i++) cout<<p[i]<<" ";
    //cout<<endl;
    //x 未満の最大の値段を特定したい
    auto f = transaction(x-1);
    /*for(auto e:f.fi) cout<<e<<" ";
    cout<<endl;
    cout<<f.se<<endl;*/
    if(f.fi.size()==1){
      p[f.fi[0]]=x-1-f.se;
      cnt[f.fi[0]]++;
      if(f.fi[0]==n-1) return;
      self(p[f.fi[0]],self);
    }
    else{
      for(auto e:f.fi) cnt[e]++;
      for(int i=f.fi.size()-1;i>=0;i--){
        if(p[f.fi[i]]) continue;
        ll s=x-1-f.se;
        for(int j=i+1;j<f.fi.size();j++) s-=p[f.fi[j]];
        ll v=s/(i+1);
        if(i==0){
          p[f.fi[0]]=v;
          if(f.fi[0]==n-1) return;
          self(p[f.fi[0]],self);
          return;
        }
        self(v+1,self);
      }
    }
  };
  solve(p[0],solve);
  //for(int i=0;i<n;i++) cout<<p[i]<<" ";
  //cout<<endl;
  for(int i=0;i<n;i++){
    while(cnt[i]<i){
      transaction(p[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