Submission #1341629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341629		hyyh	Souvenirs (IOI25_souvenirs)	C++20	21 / 100	198 ms	1416 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <map>
#include <iostream>

using namespace std;
using ll = long long;
#define endl '\n'
#define f first
#define s second

void buy_souvenirs(int N, long long P0) {
  vector<ll> minP(N);
  vector<ll> maxP(N);
  vector<int> cnt(N);
  map<int,vector<int>> wait;
  vector<pair<ll,pair<vector<int>,ll>>> query;
  int cur = N-1;
  int forfull = 0;
  minP[0] = P0;
  maxP[0] = P0;
  for(int i{1};i < N;i++){
    maxP[i] = maxP[i-1]-1;
    minP[i] = N-i;
  }
  while(cur != 0){
    // cout << "Max : ";
    // for(auto k:maxP) cout << k << " ";
    // cout << endl;
    // cout << "Min : ";
    // for(auto k:minP) cout << k << " ";
    // cout << endl;
    pair<vector<int>,ll> ret = transaction(min(maxP[forfull]-1,maxP[cur]));
    ll use = maxP[cur]-ret.s;
    query.push_back({ret.f.size(),{ret.f,use}});
    //cout << "Query : " << maxP[cur] << " " << use << endl;
    for(auto k:ret.f){
      //cout << k << " ";
      wait[k].emplace_back(query.size()-1);
      use -= minP[k];
      cnt[k]++;
    }
    //cout << endl;
    //cout << use << endl;
    maxP[ret.f.front()] = use+minP[ret.f.front()];
    for(int i{1};i < N;i++){
      maxP[i] = min(maxP[i],maxP[i-1]-1);
    }
    for(int i{N-2};i >= 0;i--){
      minP[i] = max(minP[i],minP[i+1]+1);
    }
    // cout << "Max2 : ";
    // for(auto k:maxP) cout << k << " ";
    // cout << endl;
    // cout << "Min2 : ";
    // for(auto k:minP) cout << k << " ";
    // cout << endl;
    for(auto [a,b]:query){
      if(a == 1){
        ll val = b.s;
        int notf = -1;
        for(auto k:b.f){
          if(minP[k] == maxP[k]){
            val -= minP[k];
          }
          else notf = k;
        }
        if(notf != -1){
          minP[notf] = val;
          maxP[notf] = val;
        }
      }
    }
    cur = 0;
    for(int i{1};i < N;i++){
      if(minP[i] != maxP[i]) cur = max(cur,i);
      else{
        for(auto k:wait[i]){
          query[k].f--;
        }
        wait[i].clear();
      }
    }
    for(int i{N-2};i >= 0;i--){
      minP[i] = max(minP[i],minP[i+1]+1);
    }
    // cout << "Max3 : ";
    // for(auto k:maxP) cout << k << " ";
    // cout << endl;
    // cout << "Min3 : ";
    // for(auto k:minP) cout << k << " ";
    // cout << endl;
  }
  for(int i{};i < N;i++){
    while(cnt[i] < i){
      transaction(maxP[i]);
      cnt[i]++;
    }
  }
  return;
}

Compilation message (stderr)

souvenirs.cpp: In function 'void buy_souvenirs(int, long long int)':
souvenirs.cpp:36:32: warning: narrowing conversion of 'ret.std::pair<std::vector<int>, long long int>::first.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   36 |     query.push_back({ret.f.size(),{ret.f,use}});
      |                      ~~~~~~~~~~^~

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