Submission #1252825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252825		Gabp	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

#include<bits/stdc++.h>
#include "souvenirs.h"
using namespace std;

void buy_souvenirs(int n, long long int P0) {
  vector<int> cnt(n, 0);
  vector<long long int> val(n, -1);
  val[0] = P0;
  
  vector<long long int> total(n, -1);
  vector<vector<int>> hist(n);
  
  while (true) {
    bool done = true;
    for (int i = 0; i < n; i++) if (val[i] == -1) done = false;
    if (done) break;
    
    bool flag = false;
    int idx;
    for (int i = n - 1; i >= 0; i--) {
      if (val[i] == -1 && total[i] == -1) flag = true;
      else if (flag || total[i] != -1) {
        idx = i;
        break;
      }
    }
    
    long long int query;
    if (val[idx] != -1) query = val[idx] - 1;
    else {
      vector<int> nxt;
      for (auto i: hist[idx]) {
        if (val[i] == -1) nxt.push_back(i);
        else total[idx] -= val[i];
      }
      
      hist[idx] = move(nxt);
      int a = hist[idx].size();
      if (a == 1) {
        val[idx] = total[idx];
        total[idx] = -1;
        continue;
      }
      long long int b = total[idx];
      for (int i = 0; i < a - 1; i++) {
        b -= hist[idx].back() - hist[idx][i];
      }
      
      query = b / a;
    }
    
    auto [list, left] = transaction(query);
    for (auto i: list) cnt[i]++;
    idx = list[0];
    hist[idx] = list;
    total[idx] = query - left;
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = cnt[i]; j < i; j++) transaction(val[i]);
  }
}

• 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