Submission #1207624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207624		vidux	Message (IOI24_message)	C++17	58.63 / 100	461 ms	868 KiB

message

#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

#ifndef LOCAL
#include "message.h"
#endif

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;

const int INF = 1e9;
const ll LLINF = 1e18;
const int N = 31;

#ifdef LOCAL
vb LOCAL_C;
vvb R;
std::vector<bool> send_packet(std::vector<bool> A) {
	vb ret(N);
	FOR(i, N) 
		if (LOCAL_C[i]) ret[i] = rand() % 2;
		else ret[i] = A[i];
	//cout << "sending: "; FOR(i, N) cout << ret[i] << " "; cout << endl;
	R.push_back(ret);
	//if (SZ(R) == 31) cout << endl;
	return ret;
}
#endif

void send_message(std::vector<bool> M, std::vector<bool> C) {
#ifdef LOCAL
	LOCAL_C = C;
#endif
	bool sf = 0, sb = 0;
	int idxf = 0, idxb = 0;
	FOR(i, N) {
		if (!C[i]) {
			if (sf && !idxf) idxf = i;
			sf = 1;
		}
		if (!C[N-1-i]) {
			if (sb && !idxb) idxb = i;
			sb = 1;
		}
	}
	bool reversed = idxf > idxb;
	send_packet(vector<bool>(N, reversed));
	if (reversed) reverse(ALL(C));
	vi safe;
	FOR(i, N) {
		if (SZ(safe) < 2) {
			send_packet(vector<bool>(N, C[i]));
			if (!C[i]) safe.push_back(reversed ? N-1-i : i);
		}
		else {
			vector<bool> m(N);
			vi nsafe;
			FORR(s, safe) {
				m[s] = C[i];
				if (!C[i]) nsafe.push_back(reversed ? N-1-i : i);
				i++;
				if (i == N) break;
			}
			i--;
			FORR(ns, nsafe) safe.push_back(ns);
			send_packet(m);
		}
		//FORR(s, safe) cout << s << " "; cout << endl;
		if (SZ(safe) == 16) break;
	}
	auto send = [&](vector<bool> m) -> void {
		m.resize(16);
		vector<bool> s(N);
		FOR(i, 16) {
			s[safe[i]] = m[i];
		} 
		send_packet(s);
	};
	vector<bool> sz(16);
	FOR(i, 16) sz[i] = (SZ(M) & (1 << i));
	send(sz);
	vector<bool> m;
	FOR(i, SZ(M)) {
		//cout << SZ(m) << endl;
		m.push_back(M[i]);
		if (SZ(m) == 16) { send(m); m.clear(); }
	}
	if (SZ(m)) send(m);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	reverse(ALL(R));
	bool reversed = accumulate(ALL(R.back()), 0) > 15;
	R.pop_back();
	//cout << "reversed: " << reversed << endl;
	vector<bool> C(N);
	vi safe;
	FOR(i, N) {
		if (SZ(safe) < 2) {
			bool c = accumulate(ALL(R.back()), 0) > 15;
			if (!c) safe.push_back(reversed ? N-1-i : i);
		}
		else {
			vi nsafe;
			FORR(s, safe) {
				bool c = R.back()[s];
				if (!c) nsafe.push_back(reversed ? N-1-i : i);
				i++;
				if (i == N) break;
			}
			i--;
			FORR(ns, nsafe) safe.push_back(ns);
		}
		R.pop_back();
		//FORR(s, safe) cout << s << " "; cout << endl;
		if (SZ(safe) == 16) break;
	}
	auto read = [&]() -> vector<bool> {
		vector<bool> m = R.back();
		R.pop_back();
		vector<bool> s(16);
		FOR(i, 16) {
			s[i] = m[safe[i]];
		}
		return s;
	};
	int sz = 0;
	vector<bool> szm = read();
	FOR(i, 16) sz |= (1 << i) * (szm[i]);
	vector<bool> ans;
	while (SZ(R)) {
		vector<bool> r = read();
		FOR(i, 16) ans.push_back(r[i]);
	}
	ans.resize(sz);
	return ans;
}

#ifdef LOCAL
int main() {
	int t; cin >> t;
	while (t--) {
		R.clear();
		int n; cin >> n;
		vb a(n);
		FOR(i, n) { int x; cin >> x; a[i] = x; }
		vb c(N);
		FOR(i, N) { int x; cin >> x; c[i] = x; }
		send_message(a, c);
		vb ans = receive_message(R);
		FOR(i, SZ(ans)) cout << ans[i] << " "; cout << endl;
	}
    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 48.6324 / 90