Submission #1267076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267076		comgaTramAnh	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	412 KiB

souvenirs

#include <set>
#include <utility>
#include <vector>
#include "souvenirs.h" 
void buy_souvenirs(int n, long long P0) {
  std::vector <long long> value(n, 0LL);
  value[0] = P0;
  std::vector <int> cnt(n, 0);
  std::vector <std::pair <std::set <int>, long long>> save(n); 
  while (true) {
    bool still = false;
    for (int i = 0; i < n; i++) {
      if (value[i] == 0) {
        still = true; 
      }
    }
    if (still == false) {
      break; 
    }
    bool have = false; 
    for (int i = n - 1; i >= 0; i--) {
      if (value[i] == 0) {
        have = true; 
      }
      if (value[i] != 0 && have == false) {
        continue; 
      }
      if (value[i] != 0 && have == true) {
        std::pair <std::vector <int>, long long> info = transaction(value[i] - 1); 
        long long M = value[i] - 1 - info.second; 
        std::set <int> myset; 
        std::vector <int> &v = info.first; 
        for (int j = 0; j < (int) v.size(); j++) {
          cnt[v[j]]++; 
          if (value[v[j]] != 0) {
            M -= value[v[j]]; 
          }
          else {
            myset.insert(v[j]); 
          }
        }            
        if ((int) myset.size() == 1) {
          value[*myset.begin()] = M; 
        }
        else if ((int) myset.size() > 1) {
          std::set <int>::iterator it = myset.begin();
          save[*it] = make_pair(myset, M);     
        }
        break; 
      }
      if (save[i].first.size() > 1) {   
        for (int j = 1; j < n; j++) {
          if (save[i].first.find(j) != save[i].first.end() && value[j] != 0) {
            save[i].second -= value[j];
            save[i].first.erase(save[i].first.find(j));   
          }
        }
        if ((int) save[i].first.size() == 1) {
          value[*save[i].first.begin()] = save[i].second;
          save[i].first.clear(); 
        }
        else if ((int) save[i].first.size() > 1) {              
          long long need = save[i].second / (int) save[i].first.size(); 
          std::pair <std::vector <int>, long long> info = transaction(need); 
          long long M = need - info.second; 
          std::set <int> myset; 
          std::vector <int> &v = info.first; 
          for (int j = 0; j < (int) v.size(); j++) {
            cnt[v[j]]++; 
            if (value[v[j]] != 0) {
              M -= value[v[j]]; 
            }
            else {
              myset.insert(v[j]); 
            }
          }
          if ((int) myset.size() == 1) {
            value[*myset.begin()] = M; 
          }
          else if ((int) myset.size() > 1) {
            std::set <int>::iterator it = myset.begin();
            save[*it] = make_pair(myset, M);     
          }     
        }
        break;  
      }
    }
  }
  for (int i = 1; i < n; i++) {
    while (cnt[i] < i) {
      transaction(value[i]); 
      cnt[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