Submission #1257292

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

souvenirs

#include "souvenirs.h"
#include <cassert>
#include <climits>
#include <utility>
#include <vector>
#include<bits/stdc++.h>


using namespace std;
using ret = pair<vector<int>, long long>;
using ll = long long;
#define reste second
vector<long long> cnt(100, 0), val(100, 0);
int n;
ret query(ll m){
  auto r = transaction(m);
    for(auto p:r.first)cnt[p]++;
    return r;
}
pair<ll, int> get_down(ret r, ll montant){
  ll m_unknowm = montant - r.reste, nbuk = 0;
  int id = -1;
  for(int p:r.first){
    nbuk += !(bool)val[p];
    m_unknowm -= val[p];
    if(val[p]==0)id=p;
  }
  return {(nbuk == 0 ? -1 : m_unknowm / nbuk), nbuk};
}
void solve(ll montant){
 
  
  
  ret re_p = query(montant);
  int nv = -1;
  if(get_down(re_p, montant).second == 1){
    if(montant==8)cerr<<"yep"<<endl;
    for(int p:re_p.first)if(val[p]==0)nv=p;
    val[nv] = get_down(re_p, montant).first;
  }else{
    if(montant==8)cerr<<"not confused "<< get_down(re_p, montant).second <<endl;

    auto gd = get_down(re_p, montant);
    while( gd.second > 1){
      cerr << "in while" << endl;
      assert(gd.first > 0);
      solve(gd.first);
      gd = get_down(re_p, montant);
    }
    for(int p:re_p.first)if(val[p]==0)nv=p;
    val[nv] = gd.first;
  }
  if(nv == -1)return;
  if(nv < n-1 && val[nv]>0 && val[nv+1]==0)
    solve(val[nv]-1);
  cerr << montant<<" nv : "<<nv << " " << val[nv]<<" "<<val[nv+1]<<endl;
  assert(nv == n-1 || (val[nv] && val[nv+1]));
}
void buy_souvenirs(int N, long long P0) {
  
  fill(cnt.begin(), cnt.end(),0);
  fill(val.begin(), val.end(),0);
  val[0] = P0;
  n = N;
  solve(P0-1);
  
  for(int i = 0; i < n ; i++){
    assert(cnt[i]<=i);
    while(i-cnt[i])query(val[i]);
  }
  for(int i = 0 ; i < n ; i++)cerr << val[i] << ' ' ;
  cerr << endl;

  return;
}

• 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