Submission #1250803

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

souvenirs

#include <bits/stdc++.h> 
#include "souvenirs.h" 
using namespace std;
/*pair <vector <int>, long long> transaction(long long M) {
  long long P[10] = {100, 94, 82, 44, 42, 30, 29, 28, 15, 4};
  int n = 10; 
  cout << "ask :   " << M << endl;
  vector <int> ret; 
  for (int i = 0; i < n; i++) {
    if (M >= P[i]) {
      ret.push_back(i); 
      M -= P[i]; 
    }  
  }                 
  return make_pair(ret, M);  
}   */
void buy_souvenirs(int n, long long P0) {
  vector <long long> value(n, 0LL);
  value[0] = P0;
  vector <int> cnt(n, 0);
  vector <pair <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) {
        pair <vector <int>, long long> info = transaction(value[i] - 1); 
        long long M = value[i] - 1 - info.second; 
        set <int> myset; 
        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; 
          //cout << *myset.begin() << "     " << M << endl;
        }
        else if ((int) myset.size() > 1) {
          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;
          //cout << *save[i].first.begin() << "    " << save[i].second << endl; 
          save[i].first.clear(); 
        }
        else if ((int) save[i].first.size() > 1) {              
          long long need = save[i].second / (int) save[i].first.size(); 
          pair <vector <int>, long long> info = transaction(need); 
          long long M = need - info.second; 
          set <int> myset; 
          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) {
            //cout << *myset.begin() << "     " << M << endl;
            value[*myset.begin()] = M; 
          }
          else if ((int) myset.size() > 1) {
            set <int>::iterator it = myset.begin();
            save[*it] = make_pair(myset, M);     
          }     
        }
        break;  
      }
    }
  }
  /*for (int i = 0; i < n; i++) {
    cout << cnt[i] << "    "; 
  }
  cout << endl; */
  for (int i = 1; i < n; i++) {
    while (cnt[i] < i) {
      transaction(value[i]); 
      cnt[i]++; 
    }
  }    
  /*for (int i = 0; i < n; i++) {
    if (cnt[i] != i) {
      cout << "ngu" << endl;
    }
  } */
}

• 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