message (IOI contest)
Time limit: 3 seconds | Memory limit: 2048 MB | Task type: interactive
Algorithms: graph theory, ad-hoc, constructive, functional graph

# Message

Aisha and Basma are two friends who correspond with each other.
Aisha has a message $M$, which is a sequence of $S$ bits (i.e., zeroes or ones),
 that she would like to send to Basma.
Aisha communicates with Basma by sending her **packets**.
A packet is a sequence of $31$ bits indexed from $0$ to $30$.
Aisha would like to send the message $M$ to Basma
 by sending her some number of packets.

Unfortunately, Cleopatra compromised the communication between Aisha and Basma
 and is able to **taint** the packets.
That is, in each packet Cleopatra can modify bits on exactly $15$ indices.
Specifically, there is an array $C$ of length $31$,
 in which every element is either $0$ or $1$, with the following meaning:

* $C[i] = 1$
   indicates that the bit with index $i$ can be changed by Cleopatra.
  We call these indices **controlled** by Cleopatra.
* $C[i] = 0$
   indicates that bit with index $i$ cannot be changed by Cleopatra.

The array $C$ contains precisely $15$ ones and $16$ zeroes.
While sending the message $M$, the set of indices controlled by Cleopatra stays the same for all packets.
Aisha knows precisely which $15$ indices are controlled by Cleopatra.
Basma only knows that $15$ indices are controlled by Cleopatra,
 but she does not know which indices.

Let $A$ be a packet that Aisha decides to send
 (which we call the **original packet**).
Let $B$ be the packet that is received by Basma
 (which we call the **tainted packet**).
For each $i$, such that $0 \leq i < 31$:
* if Cleopatra does not control the bit with index $i$ ($C[i]=0$),
   Basma receives bit $i$ as sent by Aisha ($B[i]=A[i]$),
* otherwise, if Cleopatra controls the bit with index $i$ ($C[i]=1$),
   the value of $B[i]$ is decided by Cleopatra.

Immediately after sending each packet,
 Aisha learns what the corresponding tainted packet is.

After Aisha sends all the packets,
 Basma receives all the tainted packets **in the order they were sent**
 and has to reconstruct the original message $M$.

Your task is to devise and implement a strategy
 that would allow Aisha to send the message $M$ to Basma,
 so that Basma can recover $M$ from the tainted packets.
Specifically, you should implement two procedures.
The first procedure performs the actions of Aisha.
It is given a message $M$
 and the array $C$,
 and should send some packets to transfer the message to Basma.
The second procedure performs the actions of Basma.
It is given the tainted packets
 and should recover the original message $M$.

## Implementation Details

The first procedure you should implement is:

```
void send_message(std::vector&lt;bool&gt; M, std::vector&lt;bool&gt; C)
```

* $M$: an array of length $S$ describing
   the message that Aisha wants to send to Basma.
* $C$: an array of length $31$
   indicating the indices of bits controlled by Cleopatra.
* This procedure may be called **at most 2100 times** in each test case.

This procedure should call the following procedure to send a packet:

```
std::vector&lt;bool&gt; send_packet(std::vector&lt;bool&gt; A)
```

* $A$: an original packet (an array of length $31$)
   representing the bits sent by Aisha.
* This procedure returns a tainted packet $B$
   representing the bits that will be received by Basma.
* This procedure can be called at most $100$ times
   in each invocation of `send_message`.

The second procedure you should implement is:

```
std::vector&lt;bool&gt; receive_message(std::vector&lt;std::vector&lt;bool&gt;&gt; R)
```

* $R$: an array describing the tainted packets.
  The packets originate from packets sent by Aisha in one `send_message` call
   and are given **in the order they were sent** by Aisha.
  Each element of $R$ is an array of length $31$, representing a tainted packet.
* This procedure should return an array of $S$ bits
   that is equal to the original message $M$.
* This procedure may be called **multiple times** in each test case,
   **exactly once** for each corresponding `send_message` call.
  The **order of** `receive_message` **procedure calls**
   is not necessarily the same as the order of the corresponding `send_message` calls.

Note that in the grading system the `send_message` and `receive_message` procedures are called in **two separate programs**.

## Constraints

* $1 \leq S \leq 1024$
* $C$ has exactly $31$ elements, out of which $16$ are equal to $0$ and $15$ are equal to $1$.

## Subtasks and Scoring

If in any of the test cases,
 the calls to the procedure ``send_packet`` do not conform to the rules mentioned above,
 or the return value of any of the calls to procedure `receive_message` is incorrect,
 the score of your solution for that test case will be $0$.

Otherwise, let $Q$ be the maximum number of calls to the procedure `send_packet`
 among all invocations of `send_message` over all test cases.
Also let $X$ be equal to:
- $1$, if $Q \leq 66$
- $0.95 ^ {Q - 66}$, if $66 < Q \leq 100$

Then, the score is calculated as follows:


| Subtask | Score  | Additional Constraints |
| :-----: | :----: | ---------------------- |
| 1       | $10 \cdot X$ | $S \leq 64$
| 2       | $90 \cdot X$ | No additional constraints.

Note that in some cases the behaviour of the grader can be **adaptive**. 
This means that the values returned by `send_packet` 
may depend not just on its input arguments but also on many other things, 
including the inputs and return values of the prior calls to this procedure 
and pseudo-random numbers generated by the grader. 
The grader is **deterministic** in the sense that if you run it twice 
and in both runs you send the same packets, it will make the same changes to them.

## Example

Consider the following call.

```
send_message([0, 1, 1, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
```

The message that Aisha tries to send to Basma is $[0, 1, 1, 0]$.
The bits with indices from $0$ to $15$ cannot be changed by Cleopatra,
 while the bits with indices from $16$ to $30$ can be changed by Cleopatra.

For the sake of this example,
 let us assume that Cleopatra fills consecutive bits she controls 
 with alternating $0$ and $1$, i.e. she assigns
 $0$ to the first index she controls (index $16$ in our case),
 $1$ to the second index she controls (index $17$),
 $0$ to the third index she controls (index $18$),
 and so on.

Aisha can decide to send two bits from the original message in one packet as follows:
 she will send the first bit at the first $8$ indices she controls
 and the second bit at the following $8$ indices she controls.

Aisha then chooses to send the following packet:

```
send_packet([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
             0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
```

Note that Cleopatra can change bits with the last $15$ indices,
 so Aisha can set them arbitrarily, as they might be overwritten.
With the assumed strategy of Cleopatra, the procedure returns:
 $[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]$.

Aisha decides to send the last two bits of $M$ in the second packet
 in a similar way as before:

```
send_packet([1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
             0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
```

With the assumed strategy of Cleopatra, the procedure returns:
 $[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]$.

Aisha can send more packets, but she chooses not to.

The grader then makes the following procedure call:

```
receive_message([[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
                  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
                 [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
                  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]])
```

Basma recovers message $M$ as follows.
From each packet she takes the first bit that occurs twice in a row,
and the last bit that occurs twice in a row.
That is, from the first packet, she takes bits $[0, 1]$, and from the second
packet she takes bits $[1, 0]$.
By putting them together, she recovers the message $[0, 1, 1, 0]$,
which is the correct return value for this call to `receive_message`.

It can be shown that with the assumed strategy of Cleopatra and for messages of length $4$,
 this approach of Basma correctly recovers $M$, regardless of the value of $C$.
However, it is not correct in the general case.

## Sample Grader

The sample grader is not adaptive.
Instead, Cleopatra fills consecutive bits she controls with alternating $0$ and $1$ bits,
 as described in the example above.

Input format: **The first line of the input contains an integer $T$,
 specifying the number of scenarios.**
$T$ scenarios follow.
Each of them is provided in the following format:

```
S
M[0]  M[1]  ...  M[S-1]
C[0]  C[1]  ...  C[30]
```

Output format:
The sample grader writes the result of each of the $T$ scenarios
 in the same order as they are provided in the input in the following format:

```
K L
D[0]  D[1]  ...  D[L-1]
```

Here, $K$ is the number of calls to `send_packet`,
 $D$ is the message returned by `receive_message`
 and $L$ is its length.


Starter code:
message.cpp: #include "message.h"

void send_message(std::vector<bool> M, std::vector<bool> C) {
  std::vector<bool> A(31, 0);
  send_packet(A);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  return std::vector<bool>({0, 1, 1, 0});
}

grader.cpp: #include "message.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>

namespace {
const int PACKET_SIZE = 31;
const int CALLS_CNT_LIMIT = 100;

int calls_cnt;
std::vector<bool> C(PACKET_SIZE);
std::vector<std::vector<bool>> R;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}

void run_scenario() {
  R.clear();
  calls_cnt = 0;

  int S;
  assert(1 == scanf("%d", &S));
  std::vector<bool> M(S);
  for (int i = 0; i < S; i++) {
    int bit;
    assert(1 == scanf("%d", &bit));
    assert((bit == 0) || (bit == 1));
    M[i] = bit;
  }

  for (int i = 0; i < PACKET_SIZE; i++) {
    int bit;
    assert(1 == scanf("%d", &bit));
    assert((bit == 0) || (bit == 1));
    C[i] = bit;
  }

  send_message(M, C);
  std::vector<bool> D = receive_message(R);

  int K = (int)R.size();
  int L = (int)D.size();
  printf("%d %d\n", K, L);
  for (int i = 0; i < L; i++)
    printf("%s%d", (i == 0 ? "" : " "), (D[i] ? 1 : 0));
  printf("\n");
}

std::vector<bool> taint(const std::vector<bool>& A) {
  std::vector<bool> B = A;
  bool bit = 0;
  for (int i = 0; i < PACKET_SIZE; i++)
    if (C[i] == 1) {
      B[i] = bit;
      bit = !bit;
    }
  return B;
}

} // namespace

std::vector<bool> send_packet(std::vector<bool> A) {
  calls_cnt++;
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if ((int)A.size() != PACKET_SIZE)
    quit("Invalid argument");

  std::vector<bool> B = taint(A);
  R.push_back(B);
  return B;
}

int main() {
  int T;
  assert(1 == scanf("%d", &T));
  for (int i = 1; i <= T; i++)
    run_scenario();
}

message.h: #include <vector>

void send_message(std::vector<bool> M, std::vector<bool> C);

std::vector<bool> send_packet(std::vector<bool> A);

std::vector<bool> receive_message(std::vector<std::vector<bool>> R);


Grader code:
grader.cpp: #include "message.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>

namespace {
const int PACKET_SIZE = 31;
const int CALLS_CNT_LIMIT = 100;

int calls_cnt;
std::vector<bool> C(PACKET_SIZE);
std::vector<std::vector<bool>> R;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}

void run_scenario() {
  R.clear();
  calls_cnt = 0;

  int S;
  assert(1 == scanf("%d", &S));
  std::vector<bool> M(S);
  for (int i = 0; i < S; i++) {
    int bit;
    assert(1 == scanf("%d", &bit));
    assert((bit == 0) || (bit == 1));
    M[i] = bit;
  }

  for (int i = 0; i < PACKET_SIZE; i++) {
    int bit;
    assert(1 == scanf("%d", &bit));
    assert((bit == 0) || (bit == 1));
    C[i] = bit;
  }

  send_message(M, C);
  std::vector<bool> D = receive_message(R);

  int K = (int)R.size();
  int L = (int)D.size();
  printf("%d %d\n", K, L);
  for (int i = 0; i < L; i++)
    printf("%s%d", (i == 0 ? "" : " "), (D[i] ? 1 : 0));
  printf("\n");
}

std::vector<bool> taint(const std::vector<bool>& A) {
  std::vector<bool> B = A;
  bool bit = 0;
  for (int i = 0; i < PACKET_SIZE; i++)
    if (C[i] == 1) {
      B[i] = bit;
      bit = !bit;
    }
  return B;
}

} // namespace

std::vector<bool> send_packet(std::vector<bool> A) {
  calls_cnt++;
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if ((int)A.size() != PACKET_SIZE)
    quit("Invalid argument");

  std::vector<bool> B = taint(A);
  R.push_back(B);
  return B;
}

int main() {
  int T;
  assert(1 == scanf("%d", &T));
  for (int i = 1; i <= T; i++)
    run_scenario();
}

message.h: #include <vector>

void send_message(std::vector<bool> M, std::vector<bool> C);

std::vector<bool> send_packet(std::vector<bool> A);

std::vector<bool> receive_message(std::vector<std::vector<bool>> R);

manager.cpp: #include "testlib.h"
#include <csignal>
#include <random>

using namespace std;


/******************************** Begin testlib-related material ********************************/

inline FILE* openFile(const char* name, const char* mode) {
	FILE* file = fopen(name, mode);
	if (!file)
		quitf(_fail, "Could not open file '%s' with mode '%s'.", name, mode);
	closeOnHalt(file);
	return file;
}


vector<FILE*> mgr2sol, sol2mgr;
FILE* log_file = nullptr;

void nullifyFile(int idx) {
	mgr2sol[idx] = sol2mgr[idx] = nullptr;
}

#ifdef __GNUC__
__attribute__ ((format (printf, 1, 2)))
#endif
void log_printf(const char* fmt, ...) {
	if (log_file) {
		FMT_TO_RESULT(fmt, fmt, message);
		fprintf(log_file, "%s", message.c_str());
		fflush(log_file);
	}
}

void registerManager(std::string probName, int num_processes, int argc, char* argv[]) {
	setName("manager for problem %s", probName.c_str());
	__testlib_ensuresPreconditions();
	testlibMode = _checker;
	random_t::version = 1; // Random generator version
	__testlib_set_binary(stdin);
	ouf.mode = _output;

	{//Keep alive on broken pipes
		//signal(SIGPIPE, SIG_IGN);
		struct sigaction sa;
		sa.sa_handler = SIG_IGN;
		sigaction(SIGPIPE, &sa, NULL);
	}

	int required_args = 1 + 2 * num_processes;
	if (argc < required_args || required_args+1 < argc) {
		string usage = format("'%s'", argv[0]);
		for (int i = 0; i < num_processes; i++)
			usage += format(" sol%d-to-mgr mgr-to-sol%d", i, i);
		usage += " [mgr_log] < input-file";
		quitf(_fail,
			"Manager for problem %s:\n"
			"Invalid number of arguments: %d\n"
			"Usage: %s",
			probName.c_str(), argc-1, usage.c_str());
	}

	inf.init(stdin, _input);
	closeOnHalt(stdout);
	closeOnHalt(stderr);

	mgr2sol.resize(num_processes);
	sol2mgr.resize(num_processes);
	for (int i = 0; i < num_processes; i++) {
		mgr2sol[i] = openFile(argv[1 + 2*i + 1], "a");
		sol2mgr[i] = openFile(argv[1 + 2*i + 0], "r");
	}

	if (argc > required_args) {
		log_file = openFile(argv[required_args], "w");
	} else {
		log_file = nullptr;
	}
}
/********************************* End testlib-related material *********************************/


// utils

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)

template<class C> int sz(const C& c) { return std::size(c); }


// grader/manager protocol

const int secret_g2m = 0x647FB390;
const int secret_m2g = 0xB107D5C0;
const int code_mask  = 0x0000000F;

const int M2G_CODE__OK = 0;
const int M2G_CODE__DIE = 1;

const int G2M_CODE__OK = 0;
const int G2M_CODE__OK_END_OF_PACKETS = 1;
const int G2M_CODE__PACKET_SIZE_INCORRECT = 2;
const int G2M_CODE__RETURN_MESSAGE_TOO_LARGE = 3;
const int G2M_CODE__PV_CALL_EXIT = 13;
const int G2M_CODE__PV_TAMPER_M2G = 14;
const int G2M_CODE__SILENT = 15;


int fifo_idx = 0;
bool mode_end_of_packets;

void out_flush() {
	fflush(mgr2sol[fifo_idx]);
}

void write_int(int x) {
	FILE* fout = mgr2sol[fifo_idx];
	if (1 != fwrite(&x, sizeof(x), 1, fout)) {
		nullifyFile(fifo_idx);
		log_printf("Could not write int to mgr2sol[%d]\n", fifo_idx);
	}
}

void write_int_array(const int* arr, int len) {
	FILE* fout = mgr2sol[fifo_idx];
	if (int ret = fwrite(arr, sizeof(int), len, fout); len != ret) {
		nullifyFile(fifo_idx);
		log_printf("Could not write int array of size %d to mgr2sol[%d], fwrite returned %d\n", len, fifo_idx, ret);
	}
}

void write_int_vector(const vector<int>& v) {
	write_int_array(v.data(), sz(v));
}


void write_secret(int m2g_code = M2G_CODE__OK) {
	write_int(secret_m2g | m2g_code);
}

#ifdef __GNUC__
__attribute__ ((format (printf, 2, 3)))
#endif
NORETURN void die(TResult result, const char* format, ...) {
	FMT_TO_RESULT(format, format, message);
	log_printf("Dying with message '%s'\n", message.c_str());
	rep(i, sz(mgr2sol))
		if(mgr2sol[i] != nullptr) {
			fifo_idx = i;
			log_printf("Sending secret with code DIE to mgr2sol[%d]\n", fifo_idx);
			write_secret(M2G_CODE__DIE);
			out_flush();
		}
	log_printf("Quitting with result code %d\n", int(result));
	quit(result, message);
}

NORETURN void die_invalid_argument(const string &msg) {
	RESULT_MESSAGE_WRONG += ": Invalid argument";
	die(_wa, "%s", msg.c_str());
}

NORETURN void die_too_many_calls(const string &msg) {
	RESULT_MESSAGE_WRONG += ": Too many calls";
	die(_wa, "%s", msg.c_str());
}

int read_int() {
	FILE* fin = sol2mgr[fifo_idx];
	int x;
	if (1 != fread(&x, sizeof(x), 1, fin)) {
		nullifyFile(fifo_idx);
		die(_fail, "Could not read int from sol2mgr[%d]", fifo_idx);
	}
	return x;
}

void read_int_array(int* arr, int len) {
	FILE* fin = sol2mgr[fifo_idx];
	if (int ret = fread(arr, sizeof(int), len, fin); len != ret) {
		nullifyFile(fifo_idx);
		die(_fail, "Could not read int array of size %d from sol2mgr[%d], fread returned %d", len, fifo_idx, ret);
	}
}


void read_secret() {
	int secret = read_int();
	if((secret & ~code_mask) != secret_g2m)
		die(_pv, "Possible tampering with sol2mgr[%d]", fifo_idx);
	int g2m_code = secret & code_mask;
	mode_end_of_packets = false;
	switch (g2m_code) {
		case G2M_CODE__OK:
			return;
		case G2M_CODE__OK_END_OF_PACKETS:
			mode_end_of_packets = true;
			return;
		case G2M_CODE__SILENT:
			die(_fail, "Unexpected g2m_code SILENT from sol2mgr[%d]", fifo_idx);
		case G2M_CODE__PV_TAMPER_M2G:
			die(_pv, "Possible tampering with mgr2sol[%d]", fifo_idx);
		case G2M_CODE__PV_CALL_EXIT:
			die(_pv, "Solution[%d] called exit()", fifo_idx);
		case G2M_CODE__PACKET_SIZE_INCORRECT:
			die_invalid_argument("Packet size is incorrect");
		case G2M_CODE__RETURN_MESSAGE_TOO_LARGE:
			die(_wa, "Returned message's length is too large.");
		default:
			die(_fail, "Unknown g2m_code %d from sol2mgr[%d]", g2m_code, fifo_idx);
	}
}


const int PACKET_SIZE = 31;
const int CALLS_CNT_LIMIT = 100;

//mt19937 rng(15061994);
//auto rnd1 =  bind(uniform_int_distribution<int>(0, (1 << 1) - 1), rng);
//auto rnd4 =  bind(uniform_int_distribution<int>(0, (1 << 4) - 1), rng);
//auto rnd31 = bind(uniform_int_distribution<int>(0, (1U << 31) - 1), rng);
int used_days, max_used_days = 0;

int compressed_len(int len) { return (len+31) / 32; }

string vi2binStr(const vector<int>& arr, int len) {
	string str(len, '*');
	rep(i, len) str[i] = (arr[i / 32] >> (i & 31) & 1) + '0';
	return str;
}

enum Strategy {
	BEGIN,
	kExampleStrategy,
	kRandom,
	kJustOnes,
	kJustZeroes,
	kMimicAllButOneRound0,
	kMimicAllButOneRound1,
	kMimicAllButOneRound2,
	kMimicAllButOneRound3,
	kMimicAllButOneRound4,
	kInvertAllButOneRound0,
	kInvertAllButOneRound1,
	kInvertAllButOneRound2,
	kInvertAllButOneRound3,
	kInvertAllButOneRound4,
	kMinimizeDiffOfZeroesAndOnes,
	kEchoPreviousResponses,
	kEchoPreviousResponsesShuffled,
	kSame,
	kFlip,
	kMimicClosestOnLeft,
	kMimicClosestOnRight,
	END
};

struct BaseTestCase {
	const int S;
	const vector<int> M_f;
	const int C_f;
};

struct EncoderTestCase {
	const BaseTestCase *base;
	Strategy strategy;
};

struct DecoderTestCase {
	const BaseTestCase *base;
	vector<int> R_f;
};


vector<BaseTestCase> ReadBaseTestCases() {
	int T = inf.readInt();
	vector<BaseTestCase> base_tests;
	for(int _ = 0; _ < T; _++) {
		int S = inf.readInt();
		vector<int> M_f(compressed_len(S), 0);
		for(int i = 0; i < S; i++) {
			int bit = inf.readInt(0, 1);
			M_f[i / 32] |= bit << (i & 31);
		}

		int C_f = 0;
		for(int i = 0; i < PACKET_SIZE; i++) {
			int ally = inf.readInt(0, PACKET_SIZE-1);
			C_f |= ally << i;
		}

		base_tests.push_back(BaseTestCase{
				.S = S,
				.M_f = M_f,
				.C_f = C_f});
	}
	fclose(stdin);
	return base_tests;
}

vector<EncoderTestCase> GenerateEncoderTests(const vector<BaseTestCase> &base_tests) {
	vector<EncoderTestCase> encoder_tests;
	if(base_tests.size() <= 3) { // This is the example test
		for(const auto &base_test : base_tests)
			encoder_tests.push_back(EncoderTestCase{
					.base = &base_test,
					.strategy = Strategy::kExampleStrategy});
	}
	else {
		for(const auto &base_test : base_tests)
			for(int strategy = Strategy::BEGIN + 1; strategy < Strategy::END; strategy++)
				encoder_tests.push_back(EncoderTestCase{
						.base = &base_test,
						.strategy = static_cast<Strategy>(strategy)});
	}

	shuffle(encoder_tests.begin(), encoder_tests.end());
	return encoder_tests;
}

void setbit(int &x, int i, int b) { b == 1 ? x |= (1 << i) : x &= ~(1 << i); }

int ApplyStrategy(const Strategy strategy, const int C_f, int used_days,
		const vector<int>& previous_answers, const vector<int>& who_to_mimic,
		const vector<int>& non_mimic_index, int x) {
	if(strategy == Strategy::kExampleStrategy) {
		int bit = 0;
		for(int i = 0; i < PACKET_SIZE; i++)
			if(C_f >> i & 1) {
				setbit(x, i, bit);
				bit ^= 1;
			}
		return x;
	}

	if(strategy == Strategy::kSame)
		return x;
	if(strategy == Strategy::kFlip)
		return x ^ C_f;
	if(strategy == Strategy::kMimicClosestOnLeft) {
		int st = __builtin_ctz(~C_f);
		int pbit = (x >> st) & 1;
		for(int dis = 1; dis < PACKET_SIZE; dis++) {
			int i = (st + dis) % PACKET_SIZE;
			if(C_f >> i & 1)
				setbit(x, i, pbit);
			pbit = (x >> i) & 1;
		}
		return x;
	}
	if(strategy == Strategy::kMimicClosestOnRight) {
		int st = __builtin_ctz(~C_f);
		int pbit = (x >> st) & 1;
		for(int dis = 1; dis < PACKET_SIZE; dis++) {
			int i = (st - dis + PACKET_SIZE) % PACKET_SIZE;
			if(C_f >> i & 1)
				setbit(x, i, pbit);
			pbit = (x >> i) & 1;
		}
		return x;
	}

	if(strategy == Strategy::kRandom)
		return x ^ (rnd.next(0U, (1U << 31) - 1) & C_f);
	if(strategy == Strategy::kJustOnes)
		return x | C_f;
	if(strategy == Strategy::kJustZeroes)
		return x & ~C_f;

	vector<char> their_choices;
	for(int i = 0; i < PACKET_SIZE; i++)
		if(!(C_f >> i & 1))
			their_choices.push_back(x >> i & 1);

	if(kMimicAllButOneRound0 <= strategy and strategy <= kInvertAllButOneRound4) {
		int id = strategy - kMimicAllButOneRound0;
		if(kInvertAllButOneRound0 <= strategy)
			id = strategy - kInvertAllButOneRound0;
		if(used_days == non_mimic_index[id]) {
			for(int i = 0; i < PACKET_SIZE; i++)
				if(C_f >> i & 1) {
					if(kMimicAllButOneRound0 <= strategy and strategy <= kMimicAllButOneRound4)
						setbit(x, i, x >> who_to_mimic[i] & 1);
					else
						setbit(x, i, (x >> who_to_mimic[i] & 1) ^ 1);
				}
			return x;
		}
		else
			return x ^ (rnd.next(0U, (1U << 31) - 1) & C_f);
	}

	if(strategy == Strategy::kMinimizeDiffOfZeroesAndOnes) {
		int zeroes_count = 0, ones_count = 0;
		for(int previous_answer: previous_answers) {
			for(int i = 0; i < PACKET_SIZE; i++)
				if((previous_answer >> i & 1) == 0)
					zeroes_count++;
				else
					ones_count++;
		}
		for(int i = 0; i < PACKET_SIZE; i++) {
			if(!(C_f >> i & 1)) {
				if((x >> i & 1) == 0)
					zeroes_count++;
				else
					ones_count++;
			}
		}
		vector<int> my_choices;
		for(int i = 0; i < (PACKET_SIZE - 1) / 2; i++) {
			int choice = rnd.next(0, 1);
			if(zeroes_count > ones_count)
				choice = 1;
			if(zeroes_count < ones_count)
				choice = 0;
			if(choice == 0)
				zeroes_count++;
			if(choice == 1)
				ones_count++;
			my_choices.push_back(choice);
		}
		shuffle(my_choices.begin(), my_choices.end());
		int ix = 0;
		for(int i = 0; i < PACKET_SIZE; i++)
			if(C_f >> i & 1)
				setbit(x, i, my_choices[ix++]);
		return x;
	}

	if(strategy == Strategy::kEchoPreviousResponses or
			strategy == Strategy::kEchoPreviousResponsesShuffled) {
		if(used_days == 1) {
			for(int i = 0; i < PACKET_SIZE; i++)
				if(C_f >> i & 1)
					setbit(x, i, rnd.next(0, 1));
		}
		else {
			int previous_response = previous_answers.back();
			vector<int> my_response;
			for(int i = 0; i < PACKET_SIZE; i++)
				if(!(C_f >> i & 1))
					my_response.push_back(previous_response >> i & 1);
			if(strategy == Strategy::kEchoPreviousResponsesShuffled)
				shuffle(my_response.begin(), my_response.end());
			int ix = 0;
			for(int i = 0; i < PACKET_SIZE; i++)
				if(C_f >> i & 1)
					setbit(x, i, my_response[ix++]);
		}
		return x;
	}

	die(_fail, "Unknown strategy!");
}

vector<int> CalculateMimicyMap(int C_f) {
	vector<int> their_indices;
	for(int i = 0; i < PACKET_SIZE; i++) {
		if(!(C_f >> i & 1))
			their_indices.push_back(i);
	}
//	shuffle(their_indices.begin(), their_indices.end(), rng);
	their_indices.erase(their_indices.begin() + rnd.next(16));
	
	vector<int> who_to_mimic(PACKET_SIZE, -1);
	int ix = 0;
	for(int i = 0; i < PACKET_SIZE; i++)
		if(C_f >> i & 1)
			who_to_mimic[i] = their_indices[ix++];
	return who_to_mimic;
}

vector<DecoderTestCase> RunEncoder(vector<EncoderTestCase> &encoder_tests) {
	int test_cases = encoder_tests.size();

	vector<DecoderTestCase> decoder_tests;

	for(int _ = 0; _ < test_cases; _++) {
		const EncoderTestCase &test = encoder_tests[_];

		write_secret();
		write_int(test.base->S);
		write_int_vector(test.base->M_f);
		write_int(test.base->C_f);
		out_flush();

		auto who_to_mimic = CalculateMimicyMap(test.base->C_f);
		vector<int> non_mimic_index(5);
		non_mimic_index[1] = rnd.next(0, 7);
		non_mimic_index[0] = rnd.next(8, 19);
		non_mimic_index[2] = rnd.next(20, 44);
		non_mimic_index[3] = rnd.next(45, 66);
		non_mimic_index[4] = rnd.next(67, 100);

		used_days = 0;
		vector<int> R_f;
		while(true) {
			read_secret();
			if(mode_end_of_packets == true) break;

			int A_f = read_int();

			if(++used_days > CALLS_CNT_LIMIT)
				die_too_many_calls("Used too many days");

			int B_f = ApplyStrategy(test.strategy, test.base->C_f, used_days, R_f, who_to_mimic, non_mimic_index, A_f);

			ensuref(((B_f ^ A_f) | test.base->C_f) == test.base->C_f, "ApplyStrategy should not edit uncontrolled bits");
			
			R_f.push_back(B_f);

			write_secret();
			write_int(B_f);
			out_flush();
		}
		decoder_tests.push_back(DecoderTestCase{
				.base = test.base,
				.R_f = R_f,
				});
		max_used_days = max(max_used_days, used_days);
	}

	write_secret();
	write_int(-1);
	out_flush();

	return decoder_tests;
}

void RunDecoder(const vector<DecoderTestCase> &decoder_tests) {
	int test_cases = decoder_tests.size();
	for(int _ = 0; _ < test_cases; _++) {
		const DecoderTestCase &test = decoder_tests[_];

		write_secret();
		write_int(sz(test.R_f));
		write_int_vector(test.R_f);
		out_flush();

		read_secret();
		int L = read_int();
		vector<int> D_f(compressed_len(L), 0);
		read_int_array(D_f.data(), sz(D_f));

		if(L != test.base->S || D_f != test.base->M_f) {
			log_printf(
					"WA:\n"
					"original message:\n"
					"'%s'\n"
					"decoded message:\n"
					"'%s'\n",
					vi2binStr(test.base->M_f, test.base->S).c_str(),
					vi2binStr(D_f, L).c_str());
	       	die(_wa, "decoded message is incorrect");
		}
	}

	write_secret();
	write_int(-1);
	out_flush();
}

int main(int argc, char **argv) {
	registerManager("message", 2, argc, argv);

	fifo_idx = 0; // Mode: Encoder
	vector<BaseTestCase> base_tests = ReadBaseTestCases();
	vector<EncoderTestCase> encoder_tests = GenerateEncoderTests(base_tests);
	vector<DecoderTestCase> decoder_tests = RunEncoder(encoder_tests);
	nullifyFile(fifo_idx);

	shuffle(decoder_tests.begin(), decoder_tests.end());

	fifo_idx = 1; // Mode: Decoder
	RunDecoder(decoder_tests);
	nullifyFile(fifo_idx);

	// scoring
	const int days_threshold = 66;
	if(max_used_days <= days_threshold)
		quitf(_ok, "Used %d days", max_used_days);
	else if(max_used_days <= CALLS_CNT_LIMIT)
		quitp(pow(0.95, max_used_days - days_threshold), "Used %d days", max_used_days);

	die(_fail, "Reached an unreachable code!!!");

	return 0;
}

stub.cpp: #include "message.h"
#include <csignal>
#include <cstdlib>
#include <cstdio>
#include <string>

using namespace std;


namespace {

/******************************** Begin testlib-related material ********************************/
#ifdef _MSC_VER
#   define NORETURN __declspec(noreturn)
#elif defined __GNUC__
#   define NORETURN __attribute__ ((noreturn))
#else
#   define NORETURN
#endif
/********************************* End testlib-related material *********************************/


// utils

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)

template<class C> int sz(const C& c) { return std::size(c); }

// grader/manager protocol

const int secret_g2m = 0x647FB390;
const int secret_m2g = 0xB107D5C0;
const int code_mask  = 0x0000000F;

const int M2G_CODE__OK = 0;

const int G2M_CODE__OK = 0;
const int G2M_CODE__OK_END_OF_PACKETS = 1;
const int G2M_CODE__PACKET_SIZE_INCORRECT = 2;
const int G2M_CODE__RETURN_MESSAGE_TOO_LARGE = 3;
const int G2M_CODE__PV_CALL_EXIT = 13;
const int G2M_CODE__PV_TAMPER_M2G = 14;
const int G2M_CODE__SILENT = 15;


bool exit_allowed = false;

NORETURN void authorized_exit(int exit_code) {
  exit_allowed = true;
  exit(exit_code);
}


FILE* fin = stdin;
FILE* fout = stdout;

void out_flush() {
	fflush(fout);
}

void write_int(int x) {
	if (1 != fwrite(&x, sizeof(x), 1, fout)) {
		fprintf(stderr, "Could not write int to fout\n");
		authorized_exit(3);
	}
}

void write_int_array(const int* arr, int len) {
	if (int ret = fwrite(arr, sizeof(int), len, fout); len != ret) {
		fprintf(stderr, "Could not write int array of size %d to fout, fwrite returned %d\n", len, ret);
		authorized_exit(3);
	}
}


void write_secret(int g2m_code = G2M_CODE__OK) {
	write_int(secret_g2m | g2m_code);
}

NORETURN void die(int g2m_code) {
	if(g2m_code == G2M_CODE__OK) {
		fprintf(stderr, "Shall not die with code OK\n");
		authorized_exit(5);
	}
	fprintf(stderr, "Dying with code %d\n", g2m_code);
	if(g2m_code != G2M_CODE__SILENT)
		write_secret(g2m_code);
	fclose(fin);
	fclose(fout);
	authorized_exit(0);
}


int read_int() {
	int x;
	if (1 != fread(&x, sizeof(x), 1, fin)) {
		fprintf(stderr, "Could not read int from fin\n");
		authorized_exit(3);
	}
	return x;
}

void read_int_array(int* arr, int len) {
	if (int ret = fread(arr, sizeof(int), len, fin); len != ret) {
		fprintf(stderr, "Could not read int array of size %d from fin, fread returned %d\n", len, ret);
		authorized_exit(3);
	}
}


void read_secret() {
	int secret = read_int();
	if((secret & ~code_mask) != secret_m2g)
		die(G2M_CODE__PV_TAMPER_M2G);
	int m2g_code = secret & code_mask;
	if(m2g_code != M2G_CODE__OK)
		die(G2M_CODE__SILENT);
}

void check_exit_protocol() {
  if (!exit_allowed)
    die(G2M_CODE__PV_CALL_EXIT);
}


// problem utils

int vb2int(const vector<bool> &v) {
	int r = 0;
	rep(i, sz(v)) r |= ((v[i] ? 1 : 0) << i);
	return r;
}

vector<bool> int2vb(int x, int len) {
	vector<bool> v(len);
	rep(i, sz(v)) v[i] = (x >> i & 1) ? true : false;
	return v;
}

void arr2vb(int* arr, int len, vector<bool> &r) {
	r.resize(len);
	rep(i, len) r[i] = (arr[i / 32] >> (i & 31) & 1) ? true : false;
}

int compressed_len(int len) { return (len+31) / 32; }

void vb2arr(vector<bool> v, int* arr, int len) {
	len = sz(v);
	rep(i, compressed_len(len)) arr[i] = 0;
	rep(i, len) arr[i / 32] |= (v[i] ? 1 : 0) << (i & 31);
}


// grader logic

const int PACKET_SIZE = 31;
const int MAX_MESSAGE_SIZE = 1024;
const int MESSAGE_SIZE_LIMIT = 2 * MAX_MESSAGE_SIZE;

NORETURN void run_encoder() {
	for(int S; read_secret(), (S = read_int()) != -1; ) {
		int M_f[(MAX_MESSAGE_SIZE + 32 - 1) / 32];
		read_int_array(M_f, compressed_len(S));
		int C_f = read_int();

		vector<bool> M;
		arr2vb(M_f, S, M);
		vector<bool> C = int2vb(C_f, PACKET_SIZE);

		send_message(M, C);

		write_secret(G2M_CODE__OK_END_OF_PACKETS);
		out_flush();
	}
	die(G2M_CODE__SILENT);
}

NORETURN void run_decoder() {
	for(int K; read_secret(), (K = read_int()) != -1; ) {
		vector<int> R_f(K, 0);
		read_int_array(R_f.data(), K);

		vector<vector<bool>> R(K);
		rep(i, K) R[i] = int2vb(R_f[i], PACKET_SIZE);
		vector<bool> D = receive_message(R);
		int L = sz(D);

		if(L < 0 || L > MESSAGE_SIZE_LIMIT) die(G2M_CODE__RETURN_MESSAGE_TOO_LARGE);

		int D_f[(MESSAGE_SIZE_LIMIT + 32 - 1) / 32];
		vb2arr(D, D_f, L);

		write_secret();
		write_int(L);
		write_int_array(D_f, compressed_len(L));
		out_flush();
	}
	die(G2M_CODE__SILENT);
}


} // namespace


vector<bool> send_packet(vector<bool> A) {
	if(sz(A) != PACKET_SIZE) die(G2M_CODE__PACKET_SIZE_INCORRECT);

	int A_f = vb2int(A);

	write_secret();
	write_int(A_f);
	out_flush();

	read_secret();
	int B_f = read_int();
	return int2vb(B_f, PACKET_SIZE);
}

int main(int argc, char **argv) {
	signal(SIGPIPE, SIG_IGN);
	atexit(check_exit_protocol);
	at_quick_exit(check_exit_protocol);

	if(argc < 2) {
		fprintf(stderr, "invalid args\n");
		authorized_exit(1);
	}

	string grader_id = argv[1];
	if (grader_id == "0")
		run_encoder();

	if (grader_id == "1")
		run_decoder();

	fprintf(stderr, "invalid grader id: '%s'\n", grader_id.c_str());
	authorized_exit(1);
}


Setup script:
#!/bin/bash
set -e # Exit immediately if a command fails

# --- Fixed Files (Problem Specific) ---
STUB_CPP="stub.cpp"        # Stub for message problem
MANAGER_CPP="manager.cpp"    # Manager for message problem
HEADER="message.h"           # Header for message problem
# TESTLIB_HEADER="testlib.h"   # Assumed present, needed by manager (Checked in original, but only needed for manager compilation)

echo "--- Setup Script ---"

# --- Argument Parsing ---
# Expect exactly one argument: solution_file
if [ "$#" -ne 1 ]; then
    echo "Usage: $0 <path/to/solution.cpp>" >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument

# --- File & Tool Checks ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools..."
check_file "$SOLUTION_CPP"
check_file "$STUB_CPP"
check_file "$MANAGER_CPP"
check_file "$HEADER"
# check_file "$TESTLIB_HEADER" # Uncomment to check for testlib.h if needed
check_tool "g++"
echo "Checks passed."
echo "Using Solution: $SOLUTION_CPP"

# --- Dynamic Naming ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
# Executable for the encoder part of the solution
ENCODER_EXE="./${SOLUTION_BASENAME}_encoder_exe"
# Executable for the decoder part of the solution
DECODER_EXE="./${SOLUTION_BASENAME}_decoder_exe"
# Executable for the manager
MANAGER_EXE="./message_manager_exe" # Keeping a fixed name for the manager executable simplifies evaluate.sh

# --- Compile ---
echo "Compiling solution and manager..."

# Compile the user solution + stub for Encoder
echo "Compiling solution for Encoder ($ENCODER_EXE)..."
g++ -std=c++17 "$SOLUTION_CPP" "$STUB_CPP" -o "$ENCODER_EXE" -I. -O2

# Compile the user solution + stub for Decoder
echo "Compiling solution for Decoder ($DECODER_EXE)..."
g++ -std=c++17 "$SOLUTION_CPP" "$STUB_CPP" -o "$DECODER_EXE" -I. -O2

# Compile the Manager
echo "Compiling Manager ($MANAGER_EXE)..."
g++ -std=c++17 "$MANAGER_CPP" -o "$MANAGER_EXE" -I. -O2

echo "Compilation finished successfully."
echo "Executables created:"
echo "  Encoder: $ENCODER_EXE"
echo "  Decoder: $DECODER_EXE"
echo "  Manager: $MANAGER_EXE"
echo "--- Setup Complete ---"

exit 0

Evaluation script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Evaluation Script ---"

# --- Argument Parsing ---
# Expect exactly two arguments: solution_file and input_file
if [ "$#" -ne 2 ]; then
    echo "Usage: $0 <path/to/solution.cpp> <path/to/input.txt>" >&2
    echo "Note: Run setup.sh <path/to/solution.cpp> first to compile." >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument
INPUT_TXT="$2"    # Get input file from second argument

# --- File & Tool Checks ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for evaluation..."
check_file "$INPUT_TXT"
check_tool "mkfifo"
check_tool "/usr/bin/time" # Check for the time command specifically
echo "Checks passed."
echo "Using Solution: $SOLUTION_CPP"
echo "Using Input:    $INPUT_TXT"

# --- Dynamic Naming (Consistent with setup.sh) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
INPUT_BASENAME=$(basename "$INPUT_TXT" .in) # Assuming .in extension for inputs
# Executable names derived from solution basename (must match setup.sh)
ENCODER_EXE="./${SOLUTION_BASENAME}_encoder_exe"
DECODER_EXE="./${SOLUTION_BASENAME}_decoder_exe"
# Fixed manager executable name (must match setup.sh)
MANAGER_EXE="./message_manager_exe"
# Final result file from the manager
RESULTS_TXT="${INPUT_BASENAME}_${SOLUTION_BASENAME}.results.txt"

# Check if executables exist (created by setup.sh)
echo "Checking for compiled executables..."
check_file "$ENCODER_EXE"
check_file "$DECODER_EXE"
check_file "$MANAGER_EXE"
echo "Executables found."

# FIFO (Named Pipe) names for Inter-Process Communication (IPC)
# Using /tmp and PID ($$) for uniqueness to allow concurrent runs
FIFO_BASE="/tmp/message_eval_${SOLUTION_BASENAME}_${INPUT_BASENAME}_$$"
MGR_TO_ENC="${FIFO_BASE}_m2e.fifo" # Manager -> Encoder pipe
ENC_TO_MGR="${FIFO_BASE}_e2m.fifo" # Encoder -> Manager pipe
MGR_TO_DEC="${FIFO_BASE}_m2d.fifo" # Manager -> Decoder pipe
DEC_TO_MGR="${FIFO_BASE}_d2m.fifo" # Decoder -> Manager pipe

# --- Cleanup Function ---
# This function will be called on script exit (normal or error)
cleanup() {
    EXIT_CODE=$? # Capture the exit code that triggered the trap
    echo "Cleaning up evaluation run (Exit Code: $EXIT_CODE)..."
    # Kill background processes if they are still running
    # Check if PIDs are set before trying to kill
    if [ -n "$ENCODER_PID" ]; then
        kill $ENCODER_PID 2>/dev/null || echo "Encoder process (PID $ENCODER_PID) already finished or failed to kill."
    fi
    if [ -n "$DECODER_PID" ]; then
        kill $DECODER_PID 2>/dev/null || echo "Decoder process (PID $DECODER_PID) already finished or failed to kill."
    fi
    # Remove FIFOs
    rm -f "$MGR_TO_ENC" "$ENC_TO_MGR" "$MGR_TO_DEC" "$DEC_TO_MGR"
    echo "Cleanup finished."
    # Exit with the original exit code
    exit $EXIT_CODE
}
# Register the cleanup function to run on EXIT signal
trap cleanup EXIT INT TERM

# --- Setup IPC ---
echo "Creating FIFOs for communication..."
mkfifo "$MGR_TO_ENC" "$ENC_TO_MGR" "$MGR_TO_DEC" "$DEC_TO_MGR"

# --- Run Processes ---
# Start solution processes in the background, connected to FIFOs

echo "Starting Encoder process (ID 0) in background..."
# The encoder stub expects argument "0"
"$ENCODER_EXE" 0 < "$MGR_TO_ENC" > "$ENC_TO_MGR" &
ENCODER_PID=$! # Store Process ID

echo "Starting Decoder process (ID 1) in background..."
# The decoder stub expects argument "1"
"$DECODER_EXE" 1 < "$MGR_TO_DEC" > "$DEC_TO_MGR" &
DECODER_PID=$! # Store Process ID

echo "Starting Manager process in foreground..."
# Manager reads test case from standard input
# Communicates with solutions via FIFOs provided as arguments
# Argument order: sol0->mgr, mgr->sol0, sol1->mgr, mgr->sol1
# Writes final result to standard output
"$MANAGER_EXE" "$ENC_TO_MGR" "$MGR_TO_ENC" "$DEC_TO_MGR" "$MGR_TO_DEC" < "$INPUT_TXT" > "$RESULTS_TXT"
MANAGER_EXIT_CODE=$? # Capture manager's exit code

# --- Wait and Check ---
# Explicitly wait for background processes (optional but good practice)
# Use wait -n to wait for the next one, or wait specific PIDs
# Suppress errors if process already finished
wait $ENCODER_PID 2>/dev/null || true
wait $DECODER_PID 2>/dev/null || true

# Check manager exit code for immediate failure indications
if [ $MANAGER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Manager process exited with non-zero status ($MANAGER_EXIT_CODE)" >&2
    # The results file might still contain useful info (e.g., WA, PV)
fi

# --- Show Result ---
echo ""
echo "--- Evaluation Result ($RESULTS_TXT) ---"
# Check if results file exists and is readable before catting
if [ -r "$RESULTS_TXT" ]; then
    cat "$RESULTS_TXT"
else
    echo "ERROR: Result file '$RESULTS_TXT' not found or not readable." >&2
fi
echo "-----------------------------------------"

echo "--- Evaluation Complete ---"

# Exit the script with the manager's exit code
# The 'trap cleanup EXIT' will run before the script finally terminates
exit $MANAGER_EXIT_CODE