oj.uz

Submission #591838

# Submission time Handle Problem Language Result Execution time Memory
591838 2022-07-08T02:07:48 Z tutis Flight to the Ford (BOI22_communication) C++17
100 / 100
 3666 ms 11392 KB 
#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int prob = 500;
#include "communication.h"
struct intervalset
{
	int sz = 0;
	vector<pair<int, int>>S;//sorted, disjoint
	intervalset()
	{

	}
	intervalset(int N)
	{
		sz = N;
		S.push_back({1, N});
	}
	void append(pair<int, int> v)
	{
		sz += v.second - v.first + 1;
		if (S.empty())
			S.push_back(v);
		else {
			assert(v.first > S.back().second);
			if (v.first == S.back().second + 1)
				S.back().second = v.second;
			else
				S.push_back(v);
		}
	}
	pair<intervalset, intervalset> split(int k)
	{	//k,sz-k
		intervalset A;
		intervalset B;
		for (pair<int, int>i : S)
		{
			if (i.second - i.first + 1 <= k)
			{
				A.append(i);
				k -= i.second - i.first + 1;
			}
			else if (k <= 0)
			{
				B.append(i);
			}
			else
			{
				A.append({i.first, i.first + k - 1});
				B.append({i.first + k, i.second});
				k = 0;
			}
		}
		return {A, B};
	}
	int kth(int k)
	{
		for (pair<int, int>i : S)
		{
			if (i.second - i.first + 1 < k)
			{
				k -= i.second - i.first + 1;
			}
			else
			{
				return i.first + (k - 1);
			}
		}
		assert(false);
		return 0;
	}
	int kelintas(int x)
	{
		int r = 0;
		for (pair<int, int>i : S)
		{
			if (i.second < x)
				r += (i.second - i.first + 1);
			else if (x < i.first)
				return 0;
			else
				return r + (x - i.first + 1);
		}
		return 0;
	}
	intervalset(const intervalset &A, const intervalset &B)
	{
		const vector<pair<int, int>>&a = A.S;
		const vector<pair<int, int>>&b = B.S;
		int i = 0;
		int j = 0;
		while (i < (int)a.size() && j < (int)b.size())
		{
			if (a[i].first < b[j].first)
				append(a[i++]);
			else
				append(b[j++]);
		}
		while (i < (int)a.size())
			append(a[i++]);
		while (j < (int)b.size())
			append(b[j++]);
	}
};
const int mxsum = 100;
pair<int, pair<int, int>> K[mxsum][mxsum];
bool prec = false;
pair<int, int> getbest(int A, int B)
{
	assert(A + B < mxsum);
	if (prec == false)
	{
		prec = true;
		for (int sum = 0; sum < mxsum; sum++)
			for (int a = 0; a <= sum; a++)
			{
				int b = sum - a;
				K[a][b] = {1000, {0, 0}};
			}
		for (int sum = 0; sum < mxsum; sum++)
		{
			if (sum <= 2)
			{
				for (int a = 0; a <= sum; a++) {
					int b = sum - a;
					K[a][b] = {0, {0, 0}};
				}
			}
			else {
				int rep = 1;
				if (sum <= 10)
					rep = 10;
				for (int r = 0; r < rep; r++)
					for (int a = 0; a <= sum; a++)
					{
						int b = sum - a;

						for (int a0 = 0; a0 <= a; a0++)
						{
							for (int b0 = 0; b0 <= b; b0++)
							{
								int a1 = a - a0;
								int b1 = b - b0;

								int a_ = a0 + b0;
								int b_ = a1;

								int a__ = a1 + b1;
								int b__ = a0;
								pair<int, pair<int, int>> gal =
								{1 + max(K[a_][b_].first, K[a__][b__].first), {a0, b0}};
								K[a][b] = min(K[a][b], gal);
							}
						}
					}
			}
		}
	}
	return K[A][B].second;
}
vector<pair<int, int>>eil;
void encode(int N, int X)
{
	intervalset A(N);
	intervalset B;
	mt19937 rng(0);
	while (A.sz + B.sz > 2)
	{
		eil.push_back({A.sz, B.sz});
		int a0 = A.sz / 2;
		int b0 = B.sz / 2;
		if (A.sz + B.sz < mxsum)
		{
			pair<int, int>c = getbest(A.sz, B.sz);
			a0 = c.first;
			b0 = c.second;
		}
		eil.push_back({a0, b0});
		eil.push_back({0, 0});
		intervalset C(A, B);
		int ka = A.kelintas(X);
		int kb = B.kelintas(X);
		int s = 1;
		if (ka != 0 && ka <= a0)
			s = 0;
		if (kb != 0 && kb <= b0)
			s = 0;
		pair<intervalset, intervalset>A_ = A.split(a0);
		pair<intervalset, intervalset>B_ = B.split(b0);
		int r = send(s);
		if (r == 0)
		{
			A = intervalset(A_.first, B_.first);
			B = A_.second;
		}
		else
		{
			A = intervalset(A_.second, B_.second);
			B = A_.first;
		}
	}
}
ld phi = (1 + sqrtl(5)) / 2;
pair<int, int> decode(int N)
{
	intervalset A(N);
	intervalset B;
	mt19937 rng(0);
	while (A.sz + B.sz > 2)
	{
		int b0 = B.sz / 2;
		int a0 = A.sz / 2;
		if (A.sz + B.sz < mxsum)
		{
			pair<int, int>c = getbest(A.sz, B.sz);
			a0 = c.first;
			b0 = c.second;
		}
		pair<intervalset, intervalset>A_ = A.split(a0);
		pair<intervalset, intervalset>B_ = B.split(b0);
		int r = receive();
		if (r == 0)
		{
			A = intervalset(A_.first, B_.first);
			B = A_.second;
		}
		else
		{
			A = intervalset(A_.second, B_.second);
			B = A_.first;
		}
	}
	if (A.sz == 0)
		return {B.S[0].first, B.S.back().second};
	if (B.sz == 0)
		return {A.S[0].first, A.S.back().second};
	return {A.S[0].first, B.S[0].first};
}
// int main()
// {
// 	int mx = 0;
// 	vector<pair<int, int>>ilg;
// 	for (int test = 0; test < 10000; test++)
// 	{
// 		int N = 1e9;
// 		int X = (asdasdasdasdasd() % N) + 1;
// 		encode(N, X);
// 		pair<int, int>a = decode(N);
// 		assert(a.first >= 1 && a.first <= N && a.second >= 1 && a.second <= N);
// 		assert(a.first == X || a.second == X);
// 		if (kiekis > mx)
// 		{
// 			ilg = eil;
// 			mx = kiekis;
// 		}
// 		kiekis = 0;
// 		eil.clear();
// 	}
// 	cout << mx << endl;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2176 KB Output is correct
2 Correct 36 ms 2000 KB Output is correct
3 Correct 41 ms 1928 KB Output is correct
4 Correct 36 ms 1916 KB Output is correct
5 Correct 32 ms 1816 KB Output is correct
6 Correct 87 ms 2176 KB Output is correct
7 Correct 58 ms 2012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 3024 KB Output is correct
2 Correct 410 ms 2604 KB Output is correct
3 Correct 487 ms 3100 KB Output is correct
4 Correct 803 ms 4024 KB Output is correct
5 Correct 698 ms 3152 KB Output is correct
6 Correct 650 ms 2948 KB Output is correct
7 Correct 2073 ms 6684 KB Output is correct
8 Correct 3611 ms 11392 KB Output is correct
9 Correct 3097 ms 8876 KB Output is correct
10 Correct 2963 ms 9012 KB Output is correct
11 Correct 3083 ms 8852 KB Output is correct
12 Correct 3144 ms 9108 KB Output is correct
13 Correct 3111 ms 9012 KB Output is correct
14 Correct 2878 ms 9000 KB Output is correct
15 Correct 1730 ms 6748 KB Output is correct
16 Correct 3666 ms 10616 KB Output is correct
17 Correct 858 ms 4504 KB Output is correct
18 Correct 821 ms 4488 KB Output is correct
19 Correct 911 ms 4728 KB Output is correct
20 Correct 830 ms 4448 KB Output is correct
21 Correct 847 ms 4476 KB Output is correct
22 Correct 817 ms 4484 KB Output is correct
23 Correct 1513 ms 4660 KB Output is correct
24 Correct 34 ms 1936 KB Output is correct
25 Correct 31 ms 1924 KB Output is correct
26 Correct 41 ms 1944 KB Output is correct
27 Correct 36 ms 1908 KB Output is correct
28 Correct 34 ms 1896 KB Output is correct
29 Correct 81 ms 2152 KB Output is correct
30 Correct 64 ms 2060 KB Output is correct