제출 #1249570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249570		PCTprobability	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	12 ms	412 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+1<n;i++){
      if(p[i]>=x&&p[i+1]<x&&p[i+1]!=0) return;
    }
    //x 未満の最大の値段を特定したい
    auto f = transaction(x-1);
    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=1;i<f.fi.size();i++){
        ll s=x-1-f.se;
        for(int j=i+1;j<f.fi.size();j++) s-=p[j];
        ll v=s/(i+1);
        self(v+1,self);
      }
    }
  };
  solve(p[0],solve);
  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: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33