Submission #1262840

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

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stdio.h>

using namespace std;

void buy_souvenirs(int N, long long P0) {
  // std::pair<std::vector<int>, long long> res = transaction(3);
  // printf("hi\n");
  vector<long long> bought(N, 0LL);
  vector<long long> solved(N, 0LL);
  vector<vector<long long> > eq;

  vector<long long> first(N + 1, 0LL);
  first[0] = 1;
  first[N] = P0;
  // printf("pushing stuff \n");
  eq.push_back(first);
  // solved[0] = P0;
  
  // start by buying P0 - 1 then 
  while(eq.size() > 0){
    // find the last equation
    // printf("getting back\n");
    vector<long long> cur = eq.back();

    // printf("got back\n");
    // first go through all the non zero ones and clean up the solves
    for (int i = 0; i < N; i++){
      if(cur[i] && solved[i]){
        cur[i] = 0;
        cur[N] -= solved[i];
      }
    }

    // if its empty then skip
    if (cur[N] == 0){
      eq.pop_back();
      continue;
    }

    // if theres only 1 bit then mark it as solved, clear it from all the predecessors

    int count = 0;
    int index = 0;
    for(int i = 0; i < N; i++){
      count += cur[i];
      if(cur[i] > 0) index = i;
    }

    long long next = 0LL;
    if (count == 1){
      solved[index] = cur[N];
      for(size_t j = 0; j < eq.size() - 1; j++){
        if(eq[j][index]){
          eq[j][index] = 0;
          eq[j][N] -= solved[index];
        }
      }

      if(index < N-1 && solved[index + 1] == 0){
        next = solved[index] - 1;
      }
      eq.pop_back();
    }else{
      // now take the floor of the value divided by the count to get the next value
      // this is guranteed to be not the biggest one
      next = cur[N] / count;
    }
    if (!next) continue;

    // do transaction now
    // cout << "Doing transaction " << next << endl;
    // printf("Doing transaction %lld\n", next);
    std::pair<std::vector<int>, long long> res = transaction(next);

    vector<long long> neweq(N + 1, 0LL);
    for(int a : res.first){
      neweq[a] = 1;
      bought[a]++;
    }
    neweq[N] = next - res.second;
    eq.push_back(neweq);
  }

  // make sure everythign is solved
  for(int i = 0; i < N; i++){
    if(!solved[i]){
      // std::cout >> "Not solved!!! " << i << " " << solved[i];
      return;
    }
  }
  // do the remaining ones now
  for(int i = 0; i < N; i++){
    while(bought[i] < i){
      std::pair<std::vector<int>, long long> res = transaction(solved[i]);
      
      if (res.second != 0 || res.first.size() != 1) {
        // std::cout >> "Not a perfect buy!! " << i << " " < <solved[i] << endl;
        return;
      }
      bought[res.first[0]]++;
    }
  }
  return;
}

• 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