oj.uz

Submission #590761

# Submission time Handle Problem Language Result Execution time Memory
590761 2022-07-06T10:32:09 Z tutis Flight to the Ford (BOI22_communication) C++17
0 / 100
 766 ms 1772 KB 
#include <bits/stdc++.h>
using namespace std;
int prob = 1;
#include "communication.h"
void encode(int N, int X)
{
	X--;
	int Y = X;
	mt19937_64 rng(1832);
	set<int>S;
	for (int t = 0; t < 1000; t++)
	{
		int i = rng() % 250;
		if (S.count(i) || S.count(i - 1) || S.count(i + 1))
			continue;
		S.insert(i);
	}
	bool ok = true;
	int c = 0;
	for (int i = 0; i < 250; i++)
	{
		if (S.count(i))
		{
			int v = 0;
			int x = send(v);
			ok = (v == x);
		}
		else if (S.count(i - 1))
		{
			if (ok)
			{
				send(X % 2);
				c++;
				if (c == 3)
				{
					X /= 2;
					c = 0;
				}
			}
			else
			{
				send(Y % 2);
				Y /= 2;
			}
		}
		else
		{
			int x = send(rng() % 2);
		}
	}
}
int fr(vector<int>x)
{
	int cnt = -1;
	int val = x[0];
	for (int i : x)
	{
		int c = 0;
		for (int j : x)
			if (i == j)
				c++;
		if (c > cnt)
		{
			val = i;
			cnt = c;
		}
	}
	return val;
}
pair<int, int> decode(int N)
{
	mt19937_64 rng(1832);
	set<int>S;
	for (int t = 0; t < 1000; t++)
	{
		int i = rng() % 250;
		if (S.count(i) || S.count(i - 1) || S.count(i + 1))
			continue;
		S.insert(i);
	}
	int a = 0;
	int b = 0;
	int ba = 1;
	int bb = 1;
	bool ok = true;
	int cnta = 0;
	int cntb = 0;
	vector<int>vals;
	for (int i = 0; i < 250; i++)
	{
		int rec = receive();
		if (S.count(i))
		{
			int v = 0;
			int x = rec;
			ok = (v == x);
		}
		else if (S.count(i - 1))
		{
			if (ok)
			{
				if (cnta <= 30)
				{
					vals.push_back(rec);
					if (vals.size() == 3)
					{
						a += fr(vals) * ba;
						ba *= 2;
						cnta++;
						vals = {};
					}
				}
			}
			else
			{
				if (cntb < 30)
				{
					b += rec * bb;
					bb *= 2;
					cntb++;
				}
			}
		}
	}
	a = max(a, 0);
	a = min(a, N - 1);
	b = max(b, 0);
	b = min(b, N - 1);
	return {a + 1, b + 1};
}
// int main()
// {
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int val = (t % 3) + 1;
// 		encode(3, val);
// 		pair<int, int>v = decode(3);
// 		assert(v.first == val || v.second == val);
// 		cout << v.first << " " << v.second << endl;
// 	}
// }

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:48:8: warning: unused variable 'x' [-Wunused-variable]
   48 |    int x = send(rng() % 2);
      |        ^

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 1772 KB Output is correct
2 Incorrect 152 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 766 ms 208 KB Not correct
2 Halted 0 ms 0 KB -