Submission #1252856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252856		zipdang04	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	13 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T> using PQMax = priority_queue<T>;
template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
  if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
  if (b < a) a = b;
}
template <class T>
void read(T &number)
{
  bool negative = false;
  register int c;
  number = 0;
  c = getchar();
  while (c != '-' && !isalnum(c)) c = getchar();
  if (c=='-'){
    negative = true;
    c = getchar();
  }
  for (; (c>47 && c<58); c=getchar())
    number = number *10 + c - 48;
  if (negative)
    number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
  read(a);
  read(args...);
}

/*
struct Node
{
  int node, len;
  Node() {node = len = 0;}
  Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/

#define fi first
#define se second

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define REV(type, i, b, a) for(type i = (b); i >= (a); i--)

#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define log2(n) (31 - __builtin_clz(n))
#define log2ll(n) (63 - __builtin_clzll(n))
#define CURRENT_TIMESTAMP chrono::steady_clock::now().time_since_epoch().count()
#define randomize mt19937_64 mt(CURRENT_TIMESTAMP)

#define MAX 105
#define MOD 1000000007

int N; ll P0;
ll prices[MAX];
int times[MAX];

pair<vector<int>, long long> callTransaction(ll m) {
    auto [bought, remain] = transaction(m);
    for (int pos: bought) times[pos]++;
    return {bought, m - remain};
}

int getSubtask() {
    if (N == 2) return 1;
    if (N == 3) return 4;
    return 0;
}
void fillTillSufficient() {
    for (int i = 2; i < N; i++) {
        while (times[i] < i) callTransaction(prices[i]);
    }
}

namespace Subtask1 {
    void solve() {
        callTransaction(P0 - 1);
    }
}

namespace Subtask4 {
    void solve() {
        auto [bought, total] = callTransaction(P0 - 1);
        if (bought.size() == 1) {
            ll P1 = total;
            callTransaction(P1 - 1);
            callTransaction(P1 - 1);
        } else {
            callTransaction((total - 1) / 2);
        }
    }
}

namespace Subtask23 {
    void solve() {
        bool last = false;
        for (int i = 1; i < N; i++) {
            ll prev = prices[i-1];
            auto [bought, total] = callTransaction(prev - 1);
            if (bought.size() == 1) 
                prices[i] = total;
            else {
                last = true;
                ll nextTransaction = (total - 1) / 2;
                ll smaller = nextTransaction - callTransaction(nextTransaction).second;
                ll bigger = total - smaller;
                prices[i] = bigger, prices[i + 1] = smaller;
                
                break;
            }
        }

        // for (ll i: prices) cerr << i << ' '; cerr << '\n';
        
    }
}

namespace Subtask5 {
    void solve() {
        for (int i = 1; i < N; i++) {
            ll money = prices[i-1] - 1;
            auto [bought, total] = callTransaction(money);
            // assert((int)bought.size() < 3);

            if (bought.size() == 1) {
                prices[i] = total;
            } else {
                ll money = (total - 1) / 2, smaller;
                std::tie(bought, smaller) = callTransaction(money);
                // assert(int(bought.size()) == 1);

                ll bigger = total - smaller;
                prices[i] = bigger, prices[i + 1] = smaller;
                i++; continue;
            }
        }
        // cerr << "done" << endl;
        fillTillSufficient();
    }
}

void clear();
void buy_souvenirs(int _N, long long _P0) {
    N = _N, P0 = _P0;
    prices[0] = P0;

    int subtask = getSubtask();
    Subtask5::solve();
    // switch (subtask)
    // {
    //     case 1: Subtask1::solve(); break;
    //     case 4: Subtask4::solve(); break;
    //     default: assert(false); break;
    // }
}
void clear() {
    // 
}

Compilation message (stderr)

souvenirs.cpp: In function 'void read(T&)':
souvenirs.cpp:29:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |   register int c;
      |                ^

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