Submission #1201960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201960		randnt93	Magic Show (APIO24_show)	C++20	0 / 100	2 ms	608 KiB

Alice

#include <vector>
#include "Alice.h"

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

int next(long& lastEven, long& lastOdd, bool odd) {
	if (odd) {
		lastOdd += 2;
		return lastOdd - 2;
	} else {
		lastEven += 2;
		return lastEven - 2;
	}
}

std::vector<std::pair<int,int>> Alice(){
	long N = 4551;
	long long X = setN(N);
	long lastEven = 2, lastOdd = 1;

	std::vector<std::pair<int, int>> output;
	for (unsigned x = 0; x < 70; x++) {
		bool kind = x % 2 == 0;
		long last = next(lastEven, lastOdd, kind);
		output.push_back({0 + 1, last + 1});

		int v = X;
		if (kind) v = ~v;
		for (int i = 0; i < 64; i++) {
			long nlast = next(lastEven, lastOdd, v & 1);
			output.push_back({last + 1, nlast + 1});
			last = nlast;
			v >>= 1;
		}
	}

	return output;
}

Bob

#include <vector>
#include "Bob.h"

enum ReplicaKind {
	RK_NORMAL = 0,
	RK_INVERTED = 1
};

long long analyze_replica(std::vector<std::vector<int>>& adj, int node, enum ReplicaKind rk) {
	int out = 0, bits = 0;
	while (true) {
		if (node % 2)
			out |= 1ll << bits;
		bits++;

		if (adj[node].empty()) break;
		node = adj[node][0];
	}

	if (rk == RK_INVERTED)
		out = ~out;
	return out;
}

long long Bob(std::vector<std::pair<int,int>> V){
	std::vector<std::vector<int>> adj;
	for (auto edge: V) {
		while (std::max(edge.first, edge.second) > adj.size())
			adj.push_back({});
		adj[edge.first - 1].push_back(edge.second - 1);
	}

	int output = 0;
	for (auto replica: adj[0]) {
		if (adj[replica].empty()) continue;
		output |= analyze_replica(adj, adj[replica][0], replica % 2 == 0 ? RK_NORMAL : RK_INVERTED);
	}

	return output;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65