제출 #1273852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273852		Ludissey	선물 (IOI25_souvenirs)	C++20	39 / 100	13 ms	396 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;


vector<pair<vector<signed>,int>> transactions;
vector<int> rem;
vector<int> val;
int N;

bool poss(int j, int x){
  int cv=1;
  vector<int> val2=val;
  val2[j]=x;
  for (int i = N-1; i >= 0; i--)
  {
    if(val2[i]!=-1) {
      if(cv>val2[i]) return false;
      cv=val2[i];
    }
    val2[i]=cv;
    cv++;  
  }
  for (auto u : transactions)
  {
    int csum=0;
    for (auto v : u.first) csum+=val2[v];
    if(csum>u.second) return false;
  }
  return true;
}

void clean_transaction(){
  for (auto u : transactions)
  {
    int rem=u.second;
    int rems=sz(u.first);
    for (auto v : u.first){
      if(val[v]!=-1) rems--;
      if(val[v]!=-1) rem-=val[v];
    }
    if(rems==1){
      for (auto v : u.first){
        if(val[v]==-1) val[v]=rem;
      }
    }
  }
}

void buy_souvenirs(signed _N, int P0) {
  N=_N;
  val.resize(N+1,-1);
  rem.resize(N,0);
  val[0]=P0;
  int j=N-1;
  for (int i = 0; i < N; i++) rem[i]=i;
  val[N]=0;
  int mx=P0-j;
  while(j>0){
    /*if(rem[j]==0) {
      j--;
      continue;
    }*/
    if(val[j]!=-1) {
      j--;
      mx=P0-j+1;
      continue;
    }

    int l=val[j+1]+1; int r=mx;
    int ans=-1;
    while(l<=r){
      int mid=(l+r)/2;
      if(poss(j,mid)){
        l=mid+1;
        ans=mid;
      }else{
        r=mid-1;
      }
    }
    ans=r;
    pair<vector<signed>, int> res=transaction(ans);
    res.second=ans-res.second;
    // cerr << ans << ": ";
    for (auto u : res.first) {
      // cerr << u << " ";
      rem[u]--;
    }
    // cerr << "\n";
    if(sz(res.first)==1) val[res.first[0]]=res.second;
    else transactions.push_back(res);
    mx--;
    clean_transaction();
  }

  for (int i = 0; i < N; i++)
  {
    while(rem[i]>0) {
      transaction(val[i]);
      rem[i]--;
    }
  }
  return;
}

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