oj.uz

답안 #1004871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004871 2024-06-21T20:59:41 Z LucaDantas Flight to the Ford (BOI22_communication) C++17
0 / 100
 2647 ms 4176 KB 
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;

struct Range {
	int l, r;
	Range(int l, int r) : l(l), r(r) {}
	int size() { return r - l + 1; }
	pair<Range, Range> split(int qtd) {
		return {Range(l, l + qtd - 1), Range(l + qtd, r) };
	}
	friend ostream& operator<<(ostream& os, const Range& r) {
		return os << '<' <<r.l << ", " << r.r << '>';
	}

};

int get_total_size(vector<Range> ranges) {
	int ans = 0;
	for(Range r : ranges)
		ans += r.size();
	return ans;
}

pair<vector<Range>, vector<Range>> split(vector<Range> ranges) {
	int sz = get_total_size(ranges);
	vector<Range> g[2];

	int now = 0;
	for(Range r : ranges) {
		if(now + r.size() <= (sz+1)/2)
			g[0].push_back(r), now += r.size();
		else if(now < (sz+1)/2) {
			auto [r1, r2] = r.split((sz+1)/2 - now);
			g[0].push_back(r1);
			g[1].push_back(r2);
			now = (sz+1)/2;
		} else
			g[1].push_back(r);
	}
	return {g[0], g[1]};
}

pair<int,int> answer(vector<Range> ranges) {
	vector<int> ans;
	for(Range r : ranges)
		for(int i = r.l; i <= r.r; i++)
			ans.push_back(i);
	return {ans[0], ans[1]};
}


pair<int,int> build_decode(vector<Range> head, vector<Range> left, vector<Range> right) {
	if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
		return answer(head);
	if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
		if(receive())
			return {head[0].l, left[0].l};
		else
			return {head[0].l, right[0].l};
	}
	if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
		if(receive() == 1)
			return answer(head);

		if(receive() == 0)
			return {head[0].l, left[0].l};
		else if(head.size() == 2)
			return {head[1].l, left[0].l};
		else
			return {head[0].r, left[0].l};

	}

	// assumes there is always the same number of people on the left and right
	int n = (int)head.size();
	vector<Range> g[2];
	pair<vector<Range>, vector<Range>> spl = split(head);
	g[0] = spl.first;
	g[1] = spl.second;

	if(get_total_size(left) > get_total_size(right))
		swap(g[0], g[1]);
	
	int k = receive();
	vector<Range> &pre = k ? right : left;

	spl = split(g[!k]);
	int m = g[!k].size();
	vector<Range> f1 = spl.first;
	vector<Range> f2 = spl.second;

	g[k].insert(g[k].end(), pre.begin(), pre.end());

	return build_decode(g[k], f1, f2);
}

bool in(vector<Range> ranges, int x) {
	for(Range r : ranges)
		if(r.l <= x && x <= r.r)
			return true;
	return false;
}

void build_encode(vector<Range> head, vector<Range> left, vector<Range> right, int secret) {
	if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
		return;
	if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
		if(in(left, secret))
			send(0);
		else // se tiver em left ou right signifca que deu errado antes entao to garantido
			send(1); // se tiver em head nao importa
		return;
	}
	if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
		if(in(left, secret)) {
			send(0), send(0); // so importa que vou pra esquerda agr, dps fds
			return;
		} else {
			int nxt = send(1);
			if(nxt) return; // fui pra direita entao ja posso terminar

			if(head[0].l == secret)
				send(0);
			else
				send(1);

			return;
		}

	}

	// assumes there is always the same number of people on the left and right
	int n = (int)head.size();
	vector<Range> g[2];
	pair<vector<Range>, vector<Range>> spl = split(head);
	g[0] = spl.first;
	g[1] = spl.second;

	if(get_total_size(left) > get_total_size(right))
		swap(g[0], g[1]);
	
	int k;
	if(in(left, secret)) {
		k = 0;
		send(0); // anterior foi mudado entao garanto movimento aqui
	} else if(in(right, secret)) {
		k = 1;
		send(1); // anterior foi mudado entao garanto movimento aqui
	} else {
		int tento = in(g[1], secret);
		k = send(tento); // tento ir pra aquele lado mas se nao for tenho que mover pro outro
	}

	vector<Range> &pre = k ? right : left;

	spl = split(g[!k]);
	int m = g[!k].size();
	vector<Range> f1 = spl.first;
	vector<Range> f2 = spl.second;

	g[k].insert(g[k].end(), pre.begin(), pre.end());

	build_encode(g[k], f1, f2, secret);
}



void encode(int N, int X) {
	vector<Range> a = {Range(1, N)};
	vector<int> s;
	return build_encode(a, {}, {}, X);
}

std::pair<int, int> decode(int N) {
	vector<Range> a = {Range(1, N)};
	vector<int> s;
	return build_decode(a, {}, {});
}

Compilation message

communication.cpp: In function 'std::pair<int, int> build_decode(std::vector<Range>, std::vector<Range>, std::vector<Range>)':
communication.cpp:76:6: warning: unused variable 'n' [-Wunused-variable]
   76 |  int n = (int)head.size();
      |      ^
communication.cpp:89:6: warning: unused variable 'm' [-Wunused-variable]
   89 |  int m = g[!k].size();
      |      ^
communication.cpp: In function 'void build_encode(std::vector<Range>, std::vector<Range>, std::vector<Range>, int)':
communication.cpp:134:6: warning: unused variable 'n' [-Wunused-variable]
  134 |  int n = (int)head.size();
      |      ^
communication.cpp:158:6: warning: unused variable 'm' [-Wunused-variable]
  158 |  int m = g[!k].size();
      |      ^

Subtask #1
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 516 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 3556 KB Output is correct
2 Correct 292 ms 3236 KB Output is correct
3 Correct 325 ms 2948 KB Output is correct
4 Correct 554 ms 3124 KB Output is correct
5 Correct 464 ms 3332 KB Output is correct
6 Correct 441 ms 3048 KB Output is correct
7 Correct 1752 ms 3244 KB Output is correct
8 Correct 2647 ms 4176 KB Output is correct
9 Correct 2324 ms 3844 KB Output is correct
10 Correct 2260 ms 3928 KB Output is correct
11 Correct 2378 ms 3556 KB Output is correct
12 Correct 2352 ms 3716 KB Output is correct
13 Correct 2367 ms 3712 KB Output is correct
14 Correct 2299 ms 4000 KB Output is correct
15 Correct 1161 ms 3420 KB Output is correct
16 Correct 2468 ms 3616 KB Output is correct
17 Correct 591 ms 3308 KB Output is correct
18 Correct 605 ms 3356 KB Output is correct
19 Correct 578 ms 3116 KB Output is correct
20 Correct 576 ms 3668 KB Output is correct
21 Correct 637 ms 3464 KB Output is correct
22 Correct 647 ms 3572 KB Output is correct
23 Correct 1070 ms 3548 KB Output is correct
24 Incorrect 2 ms 332 KB Not correct
25 Halted 0 ms 0 KB -