제출 #1256698

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

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#include <utility>
#include <vector>
using ll=long long;
using namespace std;
#define vi vector<int>
#define vl vector<ll>
using call= pair<vi,ll>;

#define pi pair<ll,ll>

pi eval(call &c , vl & sol){
  auto &[v,sum]=c;
  int count=0;
  for(int i:v){
    if(sol[i]){
      sum-=sol[i];
    }
    else count++;
  }
  return {sum,count};
}


pair<vi, ll >TRANSACTION(ll M, vi & bought ){
  auto [v,l]=transaction(M);
  for(int i:v)bought[i]++;
  return {v,l};
}

void buy_souvenirs(int N, long long P0) {
  vector<ll> sol(N);
  sol[0]=P0;
  stack<call>s;
  vi bought(N);

  s.push({vi{0},P0});
  while(!s.empty()){
    auto c=s.top();
    auto [sum,count]=eval(c,sol);
    int mean;
    if(!count){
      int i=c.first[0];
      if(i<N-1 && !sol[i+1]){
        mean=sol[i]-1;
      }
      else {
        s.pop();
        continue;
      }
    }
    else mean=sum/count;
    if(count==1){
      for(int i:c.first){
        if(!sol[i])sol[i]=sum;
      }
      continue;
    }
    
    auto [v,l]=TRANSACTION(mean,bought);
    s.push({v,mean-l});
  }
  for(int i=0;i<N;i++){
    while(bought[i]<i){
      TRANSACTION(sol[i],bought);
    }
  }
  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33