#include "light.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll goal = 3;
vector<ll> pos;
ll len;
void prepare(){
pos.clear();
pos.push_back(1);
len = 1;
}
pair<ll, vector<ll>> join(ll p){
len += p;
vector<ll> nw;
nw.push_back(len);
ll idx = pos.size() - 1;
while (nw.back() != 1) {
ll nxt = len - (len - nw.back() + 1) * (goal+1);
while (idx > 0 && pos[idx-1] + p*goal >= nxt)
idx --;
if (pos[idx] <= nxt) {
nw.push_back(nxt);
continue;
}
nw.push_back(pos[idx]);
}
reverse(nw.begin(), nw.end());
pos = nw;
return {p*goal, nw};
}
pair<ll, vector<ll>> leave(ll p){
len -= p;
vector<ll> nw;
nw.push_back(len);
ll idx;
for (ll i=pos.size()-1; i>=0; i--) {
if (pos[i] <= len) {
idx = i;
break;
}
}
while (nw.back() != 1) {
ll nxt = len - (len - nw.back() + 1) * (goal+1);
while (idx > 0 && pos[idx-1] + p*goal >= nxt)
idx --;
if (pos[idx] <= nxt) {
nw.push_back(nxt);
continue;
}
nw.push_back(pos[idx]);
}
reverse(nw.begin(), nw.end());
pos = nw;
return {p*goal, nw};
}
/*
using namespace std;
typedef long long ll;
namespace {
double maxQuotient = 0.0;
ll N = 1;
size_t maxFires = 1;
vector<ll> fires = {1};
constexpr int MAX_NUM_FIRES = 150;
[[noreturn]] void die(string msg)
{
cout << msg << endl;
exit(0);
}
void check(ll p, pair<ll, vector<ll>> res) {
ll t = res.first;
vector<ll> newFires = res.second;
maxQuotient = max(maxQuotient, static_cast<double>(t)/abs(static_cast<double>(p)));
maxFires = max(maxFires, newFires.size());
cout << (p < 0? "leave" : "join") << "(" << llabs(p) << ") returned " << t << ", {";
for(size_t i = 0; i < newFires.size(); i++) {
cout << newFires[i];
if(i + 1 < newFires.size()) cout << ", ";
}
cout << "}" << endl;
if(t < 0 || t > 5 * static_cast<__int128_t>(llabs(p))) die("Invalid return value");
for(size_t i = 0; i + 1 < newFires.size(); i++) {
if(newFires[i] >= newFires[i + 1]) die("Invalid return value");
}
if(!newFires.empty() && (newFires[0] <= 0 || newFires.back() > N)) die("Invalid return value");
if(newFires.size() > MAX_NUM_FIRES) die("Too many burning torches");
if(newFires.empty() || newFires.back() < N) die("Rightmost torch not on fire");
size_t i = 0;
for (ll x : newFires) {
for (;; ++i) {
if (i >= fires.size() || fires[i] > x) die("Not all announced torches have been lit");
if (fires[i] + t >= x) break;
}
}
fires = newFires;
}
};
int main() {
int Q;
if (!(cin >> Q)) die("Invalid input");
cout << "prepare()" << endl;
prepare();
for (int i = 0; i < Q; i++) {
ll p;
if (!(cin >> p) || p == 0) die("Invalid input");
N += p;
if (N <= 0) die("The stage is empty");
if (p > 0) check(p, join(p));
if (p < 0) check(p, leave(-p));
}
cout << "Correct: ratio at most " << maxQuotient << ", at most " << maxFires << " burning torches" << endl;
return 0;
}
Compilation message
light.cpp:62:1: error: unterminated comment
62 | /*
| ^
