Submission #1251198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251198		alecurse	선물 (IOI25_souvenirs)	C++20	25 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>
#define ll long long int
#define mp make_pair
using namespace std;

vector<pair<ll,vector<ll> > > v;
vector<ll> provvisorio;
vector<ll> calls;
vector<ll> definitivo;
void solve(ll index, long long x, ll N, ll P0) {
  pair<vector<int>, long long> pt =transaction(x);
  x-=pt.second;
  v[index].first=x;
  for(auto el : pt.first) {
    v[index].second.push_back(el);
  }
  // v[index].second=pt.first;
  // cout<<index<<": ";
  // for(auto el : pt.first) {
  //   cout<<el<<" ";
  // }
  // cout<<"\n\n\n";
  for(auto el : pt.first) {
    calls[el]++;
  }
  ll a = 1, b = P0-N+1;
  ll minsol = b;
  while(a<=b) {
    ll k = (a+b)/2;
    ll somma = 0;
    for(auto el : pt.first) {
      somma+=k+N-el-1;
    }
    if(somma>=x) {
      b=k-1;
      minsol=min(minsol,k);
    } else {
      a=k+1;
    }
  }
  provvisorio[index]=minsol+N-index-1;
}
void buy_souvenirs(int N, long long P0) {
  v.resize(N);
  calls.resize(N);
  provvisorio.resize(N);
  provvisorio[0]=P0;
  for(ll i=1;i<N;i++) {
    solve(i,provvisorio[i-1]-1,N,P0);
  }
  definitivo.resize(N);
  definitivo[0]=P0;
  for(ll i=N-1;i>=1;i--) {
    ll thsomma = v[i].first;
    for(auto el : v[i].second) {
      if(el==i)
        continue;
      thsomma-=definitivo[el];
    }
    definitivo[i]=thsomma;
  }
  // // for(ll i=0;i<N;i++) {
  // //   cout<<calls[i]<<" ";
  // // }
  for(ll i=1;i<N;i++) {
    while(calls[i]<i) {
      calls[i]++;
      transaction(definitivo[i]);
    }
  }
  return;
}

• 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