light — CEOI contest
Task type: interactive | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 20
Algorithms: ad-hoc

![](_page_0_Picture_0.jpeg)

# A Light Inconvenience (light)

The Scientific Committee is relaxing at the opening ceremony of this year's CEOI. The tasks are prepared, the grading server's 10<sup>12</sup> firewalls are finally up, and the committee is looking forward to an amazing show with flaming torches. Nothing can go wrong. Except... no one bought enough oil for those torches! Now the committee needs help to run the show without using up their oil supplies.

During the show, there will be performers standing in a line, numbered from left to right starting at 1. The number of performers will vary over time. Each performer holds a torch which may or may not be on fire at any point in time. Initially, there is only one performer whose torch is on fire.

The show is divided into acts. At the beginning of act $a$, either $p_a > 0$ performers decide to join the line on the right, or the rightmost $p_a > 0$ performers decide to leave. This is out of the committee's control. The leftmost performer always remains on stage. The torches of joining performers are not on fire, and leaving performers extinguish their torches if they are on fire.

As soon as the line of performers for act $a$ is ready, the committee has to announce a number $t_a \ge 0$. Then, each performer whose torch is on fire shares their fire with the $t_a$ performers on their right. This means that the torch of performer $i$ will be on fire afterwards if and only if the torch of at least one of the performers $\max\{i - t_a, 1\}, \dots, i$ was on fire beforehand. For a more dynamic show, $t_a$ must not be larger than $5p_a$, and should be as low as possible (see the grading section below).

At the end of each act, the committee has to tell every performer whose torch is currently on fire whether to extinguish it or not. For aesthetic reasons, the torch of the rightmost performer should always be on fire after that. Moreover, to conserve oil, the number of torches left on fire must not be larger than 150.

Write a program that tells the committee how to run the show within these constraints.

## Communication

This is a communication task. You must implement the following three functions:

*   `void prepare()` is called in the beginning. You can use this function for setup (or do nothing).
*   `pair<long long, vector<long long>> join(long long pa)` is called when $p_a > 0$ performers join the line on the right. This function must return a pair that consists of the number $t_a$ announced by the committee and the list of those performers whose torches should be on fire at the end of the act. This list must be in strictly increasing order.
*   `pair<long long, vector<long long>> leave(long long pa)` is called when the rightmost $p_a > 0$ performers leave the line. Again, it must return a pair that consists of the number $t_a$ announced by the committee and the list of those performers whose torches should be on fire at the end of the act, in strictly increasing order.

If any of your return values does not satisfy the above constraints, your program will be immediately terminated and judged as **Not correct** for the respective testcase. You must not write to standard output or read from standard input; otherwise, you may receive the verdict **Security violation!**. You are however free to write to the standard error stream (`stderr`).

You must include the file `light.h` in your source code. To test your program locally, you can link it with `sample_grader.cpp`, which can be found in the attachment for this task in cms. See below for a description of the sample grader, and see `sample_grader.cpp` for instructions on how to run it with your program. The attachment also contains a sample implementation as `light_sample.cpp`.

![](_page_1_Picture_0.jpeg)

## Constraints and grading

Let $N$ denote the maximum number of performers who are simultaneously standing in the line at any time. In all testcases, $N \le 10^{17}$ and $1 \le Q \le 50\,000$.

**Subtask 1 (5 points).** There is only one call to `leave` per testcase.

**Subtask 2 (5 points).** $N \le 700$

**Subtask 3 (10 points).** $N \le 5\,000$

**Subtask 4 (5 points).** $N \le 25\,000$

**Subtask 5 (10 points).** $N \le 100\,000$

**Subtask 6 (5 points).** $N \le 500\,000$

**Subtask 7 (60 points).** No further constraints.

**Partial scoring.** In Subtask 7, your actual score depends on the maximum value of $t_a / p_a$ over all acts $a$ according to the following table:

| max $t_a/p_a$ | [0, 1] | (1, 2] | (2, 3] | (3, 5] |
|---------------|--------|--------|--------|--------|
| score         | 60     | 35     | 20     | 10     |

In particular, to get full score all return values of `join` and `leave` must satisfy $t_a \le p_a$.

## Example interaction

Consider a testcase with $Q = 4$. Here, an interaction between your program and the grader could look as follows:

| Call      | Return value | Explanation                                                                                                                                                                                                                         |
|-----------|--------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| prepare() | —            | you're free to do any setup here (or do nothing)<br>the ceremony starts with one performer whose torch is on fire<br>Image: torch                                                                                                   |
| join(3)   | 3, {2, 4}    | three performers join for a total of four performers<br>performer 1 lights the torches of performers 2, 3, and 4;<br>afterwards, performers 1 and 3 extinguish their torches<br>Image: torch, torch, torch                          |
| leave(2)  | 0, {2}       | the two rightmost performers leave (only two remain)<br>no new torches are lit; the torch of performer 2 remains on fire<br>Image: torch                                                                                            |
| join(2)   | 3, {2, 4}    | two new performers join (for a total of four)<br>performer 2 lights the torches of performers 3 and 4;<br>performer 3 extinguishes their torch afterwards<br>Image: torch, torch, torch                                             |
| join(3)   | 3, {2, 4, 7} | three new performers join (for a total of seven)<br>first the torches of performers 3, 5, 6, and 7 are lit, then<br>performers 3, 5, and 6 extinguish their torches again<br>Image: torch, torch, torch, torch, torch, torch, torch |

![](_page_2_Picture_0.jpeg)

The above interaction is reproduced by `light_sample.cpp` on the public testcase.

Note that the above sequence of calls to `join` and `leave` would constitute a valid testcase in any of the subtasks.

## Grader

The sample grader first expects on standard input the integer $Q$. It then writes to standard output a protocol of all calls to the above three functions.

In the beginning, the grader calls `prepare()`. Then it simulates the $Q$ acts. For each act $a$, it expects on standard input either an integer $p_a > 0$, meaning that $p_a$ performers join the line, or an integer $q_a < 0$, meaning that $p_a := -q_a$ performers leave the line; it will then call `join(pa)` or `leave(pa)`, respectively. Upon termination, it writes one of the following messages to standard output:

**Invalid input.** The input to the grader via standard input was not of the above form.

**The stage is empty.** There is less than one performer left.

*   **Invalid return value.** The return value $t_a$ does not satisfy $0 \le t_a \le 5p_a$, the list of performers was not given in strictly increasing order, or the list of performers contains an integer smaller than 1 or larger than the total number of performers on stage.
*   **Too many burning torches.** More than 150 torches were on fire after the act.
*   **Rightmost torch not on fire.** The rightmost torch was not lit, or it was extinguished.
*   **Not all announced torches have been lit.** The torch of at least one of the performers returned by your function has not been lit.
*   **Correct: ratio at most** *f*, **at most** *b* **burning torches.** None of the above errors occurred, all calls to `leave` and `join` satisfied $t_a \le f \cdot p_a$ (up to rounding errors), and there were at most $b$ torches on fire after any act.

In contrast, the grader actually used to judge your program will only output **Not correct** (for any of the above errors), **Security violation!**, **Partially correct**, or **Correct**. Moreover, the grader is *adaptive*, i.e. the number of performers joining or leaving in each act may depend on the behavior of your program in the current as well as in earlier runs. Both the sample grader and the grader used to judge your program will terminate your program automatically whenever one of the above errors occurs.

## Limits

Time: 1 s

Memory: 512 MiB

Starter code:
grader.cpp: /*
SAMPLE GRADER for task LIGHT

USAGE:
place together with your solution and light.h in the same directory, then:
g++ <flags> sample_grader.cpp <solution_file>
e.g.:
g++ -std=c++17 sample_grader.cpp light.cpp

INPUT/OUTPUT:
The sample grader first expects on standard input the integer Q. It then writes
to standard output a protocol of all calls to the three functions prepare, join,
and leave.

In the beginning, the grader calls prepare(). Then it simulates the Q acts. For
each act a, it expects on standard input either an integer p_a > 0, meaning that
p_a performers join the line, or an integer q_a < 0, meaning that p_a = -q_a
performers leave the line; it will then call join(p_a) or leave(p_a),
respectively.

Upon termination, it writes your verdict to standard output.
*/
#include "light.h"
#include <iostream>
#include <string>
#include <vector>

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;
}

interactor.cpp: // Author: HeRaNO
// adapted from manager.cpp, testlib version

// #define DEBUG

// #include <managerframework.h>
// #include <bits/stdc++.h>

#include "testlib.h"
#include <random>
#include <cassert>

constexpr int TCOEFF = 5;
float _score[] = {1.0, 1.0, 0.5833333333333334, 0.3333333333333333, 0.16666666666666666, 0.16666666666666666};

using namespace std;
typedef long long ll;

int FIRELIMIT;
ll MAX_N;

#ifdef DEBUG
	#define SECURITY_VIOLATION "Security violation!"
	#define NOT_ORDERED "Positions not ordered or not unique"
	#define TOO_MANY_FIRES "Too many fires"
	#define GONE_TOO_FAR "Too large t"
	#define CORRECT(x) "Correct: coefficient <= %lld", x
	#define NOT_LIT(x) "Torch %lld not lit (t too small)", x + 1
	#define OUT_OF_RANGE(x) "Runner %lld out of range", x + 1
	#define T_OUT_OF_RANGE "Invalid value for t (t < 0)"
	#define RIGHTMOST_NOT_LIT "Rightmost torch not lit"
#else
	#define SECURITY_VIOLATION "Security violation!"
	#define NOT_ORDERED "Not correct"
	#define TOO_MANY_FIRES "Not correct"
	#define GONE_TOO_FAR "Not correct"
	#define CORRECT(x) x == 1? "Correct" : "Partially correct"
	#define NOT_LIT(x) "Not correct"
	#define OUT_OF_RANGE(x) "Not correct"
	#define T_OUT_OF_RANGE "Not correct"
	#define RIGHTMOST_NOT_LIT "Not correct"
#endif

namespace {
	constexpr int ANSWER = 324137656;
}

void result(double _, const char *msg, ...) {
	va_list args;
  va_start(args, msg);
	quitf(_wa, msg, args);
}

void result(vector<float> v_score, vector<string> verdict) {
	double score = v_score.back();
	if (score == 1.0) {
		quitf(_ok, "%s", verdict.back().c_str());
	} else {
		quitp(score * 100, "%s", verdict.back().c_str());
	}
}

#define write(x) _write_helper(__LINE__, x)
template<typename T> void _write_helper(int line, T t) {
    fwrite(&t, sizeof(t), 1, stdout);
    fflush(stdout);

    #ifdef DEBUG_
        cerr << "[line" << line << "] " << t << flush;
    #endif
}

template<typename T> T read_or_fail() {
	T x;
	if (fread(&x, sizeof(x), 1, stdin) != 1)
		result(0.0, SECURITY_VIOLATION);
	return x;
}

pair<__int128_t, vector<ll>> read_fires() {
	int code = read_or_fail<int>();
	ll t = read_or_fail<ll>();
	int size = read_or_fail<int>();
	if(code != ANSWER)
		result(0.0, SECURITY_VIOLATION);
	if(t < 0)
		result(0.0, T_OUT_OF_RANGE);

	if(size < 0 or size > 2 * FIRELIMIT) result(0.0, SECURITY_VIOLATION);
	vector<ll> r(size);
	if(fread(r.data(), sizeof(ll), size, stdin) != size)
		result(0.0, SECURITY_VIOLATION);
	if(size > FIRELIMIT) result(0.0, TOO_MANY_FIRES);
	for(int i = 1; i < size; ++i)
		if(r[i] <= r[i - 1]) result(0.0, NOT_ORDERED);
	for(auto x : r)
		if(x < 0) result(0.0, OUT_OF_RANGE(x));
	for(auto &x : r) --x;

	return {t, r};
}

mt19937_64 eng;

#define rnd Rnd

ll rnd(ll l, ll h) {
	uniform_int_distribution<ll> distr(l, h);
	return distr(eng);
}

class abstract_adversary {
  public:
    abstract_adversary() : N(0), fires(1, 0) {}
	virtual ~abstract_adversary() {}

	virtual ll next_act() = 0;

	virtual void light(const vector<ll> &new_fires, ll t) {
		check(new_fires, t);
		fires = new_fires;
	}

  protected:
	ll N;
	vector<ll> fires;

	virtual void check(const vector<ll> &new_fires, __int128_t t) {
		if(t < 0) result(0.0, T_OUT_OF_RANGE);

		size_t i = 0;
		for(auto x : new_fires) {
			if(x < 0 or x > N) result(0.0, OUT_OF_RANGE(x));

			for(;; ++i) {
				if(i >= fires.size() or fires[i] > x) result(0.0, NOT_LIT(x));
				if(fires[i] + t >= x) break;
			}
		}

		if(new_fires.empty() or new_fires.back() != N)
			result(0.0, RIGHTMOST_NOT_LIT);
	}
};

class sample_adversary : public abstract_adversary {
  public:
	sample_adversary() : abstract_adversary(), counter(0) {}
	virtual ~sample_adversary() {}

	virtual ll next_act() {
		ll delta = ops[counter++];
		N += delta;
		return delta;
	}

  protected:
	int counter;

	static constexpr ll ops[] = {3, -2, 2, 3, 0};
};

class random_adversary : public abstract_adversary {
  public:
	random_adversary() : abstract_adversary() {}
	virtual ~random_adversary() {}

	virtual ll next_act() {
		ll new_N = next_act_internal();
		ll delta = new_N - N;
		N = new_N;
		assert(0 <= N and N < MAX_N);
		return delta;
	}

  protected:
	virtual ll next_act_internal() {
		ll new_N = N;
		while(new_N == N) new_N = rnd(0, MAX_N - 1);
		return new_N;
	}
};

class greedy_adversary : public random_adversary {
  public:
	greedy_adversary() : random_adversary() {}
	virtual ~greedy_adversary() {}

  protected:
	virtual ll next_act_internal() {
		if(rnd(1, 100) <= 42 or fires.size() < 10)
			return random_adversary::next_act_internal();

		int lower = rnd(0, 1)? 2 : (int) fires.size() / 2;
		int i = (int) rnd(lower, fires.size() - 2);
		return fires[i] - rnd(0, 2);
	}
};

class dismantle_adversary : public random_adversary {
  public:
	dismantle_adversary() : random_adversary() {}
	virtual ~dismantle_adversary() {}

  protected:
	virtual ll next_act_internal() {
		if(fires.size() <= 2)
			return random_adversary::next_act_internal();
		for(int i = (int) fires.size() - 1; i >= 0; --i)
			if(fires[i] < .95 * N) return max(0ll, fires[i] - rnd(1, 2));
		return random_adversary::next_act_internal();
	}
};

class babystep_adversary : public random_adversary {
  public:
	babystep_adversary() : random_adversary() {}
	virtual ~babystep_adversary() {}

  protected:
	virtual ll next_act_internal() {
		return rnd(0, 1) or N <= 1? random_adversary::next_act_internal() : N - 1;
	}
};

class precomputed_adversary : public abstract_adversary {
  public:
	precomputed_adversary(size_t Q) : abstract_adversary() {
		while(pos.size() < Q) pos.insert(rnd(1, MAX_N - 1));
	}
	virtual ~precomputed_adversary() {}

	virtual ll next_act() {
		ll x = next_act_internal() - N;
		N += x;
		assert(0 <= N and N < MAX_N);
		return x;
	}

  protected:
	virtual ll next_act_internal() = 0;
	set<ll> pos;
};

class one_leave_adversary : public precomputed_adversary {
  public:
	one_leave_adversary(size_t Q) : precomputed_adversary(Q - 1) {}
	virtual ~one_leave_adversary() {}

  protected:
	virtual ll next_act_internal() {
		if(pos.empty()) return rnd(1, N);
		ll next = *pos.begin(); pos.erase(pos.begin());
		assert(next > N);
		return next;
	}
};

class one_leave_extra_adversary : public one_leave_adversary {
  public:
	one_leave_extra_adversary(size_t Q) : one_leave_adversary(Q), Q(Q), called_leave(false) {}
	virtual ~one_leave_extra_adversary() {}

  protected:
	virtual ll next_act_internal() {
		if(pos.empty()) return rnd(1, N);
		if(not called_leave and pos.size() <= Q / 2) {
			ll x = rnd(1, MAX_N - 1);
			if(x < N) {
				called_leave = true;
				Q = min(Q, MAX_N - N - 1);
				while(pos.size() < Q) pos.insert(rnd(x + 1, MAX_N - 1));
				return x;
			}
		}

		ll next = *pos.begin(); pos.erase(pos.begin());
		assert(next > N);
		return next;
	}

	ll Q;
	bool called_leave;
};

class onezero_adversary : public random_adversary {
  public:
	onezero_adversary(int Q) : random_adversary(), Q(Q), counter(0) {}
	virtual ~onezero_adversary() {}

  protected:
	virtual ll next_act_internal() {
		++counter;
		if(counter == 1)     return rnd(MAX_N / 3, MAX_N / 2);
		if(counter == 2*Q/3) return 0;
		else                 return N + (rnd(0, 1)? 1 : rnd(1, 4711));
	}

	int Q;
	int counter;
};

class up_down_adversary : public abstract_adversary {
  public:
	up_down_adversary() : abstract_adversary(), todo(), phase(DOWN) {}
	virtual ~up_down_adversary() {}

	virtual ll next_act() {
		if(todo.empty()) toggle_phase();
		assert(not todo.empty());
		ll r = todo.back(); todo.pop_back();
		N += r;
		assert(0 <= N and N < MAX_N);
		return r;
	}

  protected:
	virtual void toggle_phase() {
		assert(todo.empty());
		if(phase == UP) phase = DOWN, init_down();
		else            phase = UP,   init_up();
	}

	virtual void init_up() = 0;
	virtual void init_down() = 0;

	vector<ll> todo;
	enum {UP, DOWN} phase;
};

class step_up_down_adversary : public up_down_adversary {
  public:
	step_up_down_adversary(int perc) : up_down_adversary(), perc(perc) {}
	virtual ~step_up_down_adversary() {}

  protected:
	virtual void init_up() {
		if(uniform_int_distribution<>(1, 100)(eng) <= perc) {
			ll low = max(MAX_N - 100000, MAX_N / 2);
			todo.push_back(rnd(low, MAX_N - 1) - N);
		}
		else {
			ll high = min(471142ll, MAX_N / 2);
			assert(high > 1);
			todo.push_back(rnd(1, high) - N);
		}
	}

	virtual void init_down() {
		ll steps = rnd(1, 1337);
		ll X = N;

		for(int i = 0; i < steps; ++i) {
			int upper = 42;
			if(N <= 5000) upper = 5;
			todo.push_back(-rnd(1, upper));
			X += todo.back();

			if(X < 0) {
				todo.pop_back();
				return;
			}
		}

		for(int i = 0; i < steps; ++i) todo.push_back(-(X / steps));

		shuffle(todo.begin(), todo.end(), eng);
		todo.resize(2 * todo.size() / 3);
	}

	int perc;
};

class countdown_adversary : public up_down_adversary {
  public:
	countdown_adversary() : up_down_adversary() {}
	virtual ~countdown_adversary() {}

  protected:
	virtual void init_up() {
		ll x; for(x = N; x == N; x = rnd(MAX_N/2, MAX_N - 1));
		todo.push_back(x - N);
	}

	virtual void init_down() {
		ll steps = min(471ll, N);
		ll upper = rnd(1, 100) <= 42? min(10ll, N / steps) : 1;
		for(ll i = 0; i < steps; ++i) todo.push_back(-rnd(1, upper));
	}
};

class revstep_up_down_adversary : public up_down_adversary {
  public:
	revstep_up_down_adversary() : up_down_adversary() {}
	virtual ~revstep_up_down_adversary() {}

  protected:
  	virtual void init_down() {
		ll low = min(100000ll, MAX_N / 10);
		todo.push_back(rnd(0, low) - N);
	}

	virtual void init_up() {
		ll steps = rnd(1, 1337);
		ll X = N;

		for(int i = 0; i < steps; ++i) {
			todo.push_back(rnd(1, 5));
			X += todo.back();

			if(X >= MAX_N) {
				todo.pop_back();
				if(todo.empty()) todo.push_back(-1);
				return;
			}
		}

		for(int i = 0; i < steps; ++i) todo.push_back((MAX_N - 1 - X) / steps);

		shuffle(todo.begin(), todo.end(), eng);
		todo.resize(2 * todo.size() / 3);
	}
};

class one_join_adversary : public precomputed_adversary {
  public:
	one_join_adversary(size_t Q) : precomputed_adversary(Q) {}
	virtual ~one_join_adversary() {}

  protected:
	virtual ll next_act_internal() {
		auto it = pos.end(); --it;
		ll x = *it; pos.erase(it);
		assert(N == 0 or x < N);
		return x;
	}
};

class kill_adversary : public random_adversary {
  public:
	kill_adversary(int factor, abstract_adversary *adv, bool stop_after_kill) :
		random_adversary(), factor(factor), internal_adv(adv),
		random_phase(false), stop_after_kill(stop_after_kill) {}
	virtual ~kill_adversary() { delete internal_adv; }

	virtual ll next_act() {
		// did we kill the solution?
		if(random_phase and stop_after_kill)
			return 0;

		// can we?
		ll to_leave = attempt_kill();
		if(to_leave) {
			#ifdef DEBUG
				if(not random_phase) fprintf(stderr,"<kill!>");
			#endif

			N -= to_leave;
			random_phase = true;
			return -to_leave;
		}

		// ... no, we can't :(
		if(random_phase) return random_adversary::next_act();

		ll r = internal_adv->next_act();
		N += r;
		return r;
	}

	virtual void light(const vector<ll> &new_fires, ll t) {
		if(random_phase) random_adversary::light(new_fires, t);
		else             internal_adv->light(new_fires, t);

		fires = new_fires;
	}

  protected:
	ll attempt_kill() {
		pair<__int128_t, ll> opt(0, 0);

		for(size_t i = 1; i < fires.size(); ++i) {
			ll to_leave = N + 1 - fires[i];
			__int128_t cost = fires[i] - fires[i - 1] - 1;

			if(cost > factor * to_leave)
				opt = max(opt, make_pair((cost + to_leave - 1) / to_leave, -to_leave));
		}

		return -opt.second;
	}

	__int128_t factor;
	abstract_adversary *internal_adv;
	bool random_phase;
	bool stop_after_kill;
};

void check() {
	// assert(fscanf(fin, "%d %lld", &FIRELIMIT, &MAX_N) == 2);
	FIRELIMIT = inf.readInt();
	MAX_N = inf.readLong();

	int Q; char buffer[512];
	// assert(fscanf(fin, "%d %s", &Q, buffer) == 2);
	Q = inf.readInt();
	string strategy = inf.readToken();

	// string strategy(buffer);
	int kill = 0, stop_after_kill;
	if(strategy == "kill") {
		// assert(fscanf(fin, "%d %d %s", &kill, &stop_after_kill, buffer) == 3);
		kill = inf.readInt();
		stop_after_kill = inf.readInt();
		strategy = inf.readToken();
	}
	// strategy = buffer;

	ll seed; // assert(fscanf(fin, "%lld", &seed) == 1);
	seed = inf.readLong();
	eng.seed(seed); eng.discard(133742);

	abstract_adversary *adv;
	     if(strategy == "rand")            adv = new random_adversary();
	else if(strategy == "greedy")          adv = new greedy_adversary();
	else if(strategy == "dism")            adv = new dismantle_adversary();
	else if(strategy == "one-zero")        adv = new onezero_adversary(Q);
	else if(strategy == "one-leave")       adv = new one_leave_adversary(Q);
	else if(strategy == "one-leave-extra") adv = new one_leave_extra_adversary(Q);
	else if(strategy == "one-join")        adv = new one_join_adversary(Q);
	else if(strategy == "baby")            adv = new babystep_adversary();
	else if(strategy == "step")            adv = new step_up_down_adversary(100);
	else if(strategy == "step2")           adv = new step_up_down_adversary(25);
	else if(strategy == "revs")            adv = new revstep_up_down_adversary();
	else if(strategy == "doom")            adv = new countdown_adversary();
	else if(strategy == "sample")          adv = new sample_adversary();
	else                                   throw -41;

	if(kill) adv = new kill_adversary(kill, adv, stop_after_kill);

	assert(strategy != "one-leave" or not kill or stop_after_kill);
	assert(strategy != "one-leave-extra" or not kill);

	bool only_one_leave = (strategy == "one-leave" or strategy == "one-leave-extra");
	int num_neg = 0;

	size_t max_fires = 1;
	__int128_t worst_coeff = 1;
	for(int act = 0; act < Q; ++act) {
		ll d = adv->next_act();
		if(d == 0) break;
		if(d < 0) ++num_neg;
		assert(num_neg <= 1 or not only_one_leave);
		if(num_neg > 1 and only_one_leave) break;
		write(d);

		auto [t, fires] = read_fires();
		max_fires = max(max_fires, fires.size());
		adv->light(fires, t);

		if(d < 0) d = -d;
		worst_coeff = max(worst_coeff, (t + d - 1) / d);
		if(worst_coeff > TCOEFF) result(0.0, GONE_TOO_FAR);
	}

	#ifdef DEBUG
		fprintf(stderr, "(%d)", (int) max_fires);
		fprintf(stderr, "[%lld]", worst_coeff);
	#endif

	sprintf(buffer, CORRECT(worst_coeff));
	result(vector<float>({1.0f, _score[worst_coeff]}), vector<string>({"Correct", buffer}));
}

int main(int argc, char *argv[]) {
	registerInteraction(argc, argv);

	check();
	return 0;
}

light.h: #include <vector>
#include <cstdio>
#include <cstdlib>
#include <optional>
#include <utility>

using namespace std;

void prepare();
std::pair<long long, std::vector<long long>> join(long long);
std::pair<long long, std::vector<long long>> leave(long long);

namespace {
	constexpr int ANSWER = 324137656;
}

template<typename T> void write(T t) {
    fwrite(&t, sizeof(t), 1, stdout);
}

template<typename T> optional<T> read() {
	T x;
	if(fread(&x, sizeof(x), 1, stdin) != 1)
		return nullopt;
	return x;
}

void output(pair<long long, vector<long long>> res) {
	write<int>(ANSWER);
	write<long long>(res.first);
	int size = min(300, (int) res.second.size());
	write<int>(size);
	fwrite(res.second.data(), sizeof(long long), size, stdout);
	fflush(stdout);
}

int main() {
	prepare();
	while(true) {
		optional<long long> d = read<long long>();
		if(not d or *d == 0)
			break;
		else if (*d > 0)
			output(join(*d));
		else
			output(leave(-(*d)));
	}
	return 0;
}