oj.uz

답안 #592003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592003 2022-07-08T11:10:53 Z tutis Flight to the Ford (BOI22_communication) C++17
100 / 100
 5080 ms 14564 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 {
			if (v.first > S.back().second)
			{
				if (v.first == S.back().second + 1)
					S.back().second = v.second;
				else
					S.push_back(v);
			}
			else
			{
				assert(v.first >= S.back().first);
				if (v.second > S.back().second) {
					sz -= S.back().second - v.first + 1;
					S.back().second = v.second;
				}
			}
		}
	}
	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 = 200;
pair<int, pair<int, int>> K[mxsum][mxsum];
bool prec = false;
pair<int, int> getbest(int A, int B)
{
	if (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 {
					bool rep = true;
					while (rep)
					{
						rep = false;
						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;
									int g = 1 + max(K[a_][b_].first, K[a__][b__].first);
									if (K[a][b].first > g)
									{
										K[a][b] = {g, {a0, b0}};
										rep = true;
									}
								}
							}
						}
					}
				}
			}
		}
		return K[A][B].second;
	}
	else
	{
		return {A / 2, B / 2};
	}
}
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});
		pair<int, int>c = getbest(A.sz, B.sz);
		int a0 = c.first;
		int 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;
		}
	}
}
pair<int, int> decode(int N)
{
	intervalset A(N);
	intervalset B;
	mt19937 rng(0);
	while (A.sz + B.sz > 2)
	{
		pair<int, int>c = getbest(A.sz, B.sz);
		int a0 = c.first;
		int 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 < 100; test++)
// 	{
// 		int N = 3 + asdasdasdasdasd() % ((int)1e9 - 3 + 1);
// 		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;
// 		}
// 		if (test % 10 == 0)
// 			cout << kiekis << endl;
// 		kiekis = 0;
// 		eil.clear();
// 	}
// }

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 2708 KB Output is correct
2 Correct 407 ms 2616 KB Output is correct
3 Correct 376 ms 2740 KB Output is correct
4 Correct 354 ms 2632 KB Output is correct
5 Correct 401 ms 2608 KB Output is correct
6 Correct 886 ms 3620 KB Output is correct
7 Correct 383 ms 2696 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1160 ms 3932 KB Output is correct
2 Correct 803 ms 3312 KB Output is correct
3 Correct 722 ms 3784 KB Output is correct
4 Correct 1190 ms 4956 KB Output is correct
5 Correct 1111 ms 3800 KB Output is correct
6 Correct 1023 ms 3800 KB Output is correct
7 Correct 2744 ms 8004 KB Output is correct
8 Correct 5080 ms 14564 KB Output is correct
9 Correct 4154 ms 11148 KB Output is correct
10 Correct 4339 ms 11236 KB Output is correct
11 Correct 3937 ms 10952 KB Output is correct
12 Correct 4205 ms 11168 KB Output is correct
13 Correct 4015 ms 11188 KB Output is correct
14 Correct 4091 ms 11144 KB Output is correct
15 Correct 2309 ms 8104 KB Output is correct
16 Correct 3912 ms 12352 KB Output is correct
17 Correct 1651 ms 5960 KB Output is correct
18 Correct 1547 ms 6056 KB Output is correct
19 Correct 1599 ms 6192 KB Output is correct
20 Correct 1543 ms 5948 KB Output is correct
21 Correct 1588 ms 6192 KB Output is correct
22 Correct 1486 ms 5820 KB Output is correct
23 Correct 1959 ms 6116 KB Output is correct
24 Correct 407 ms 2600 KB Output is correct
25 Correct 423 ms 2612 KB Output is correct
26 Correct 358 ms 2624 KB Output is correct
27 Correct 362 ms 2600 KB Output is correct
28 Correct 349 ms 2608 KB Output is correct
29 Correct 854 ms 3668 KB Output is correct
30 Correct 437 ms 2596 KB Output is correct