Submission #1206581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206581		vidux	메시지 (IOI24_message)	C++17	0 / 100	78 ms	840 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) {
	int sent = 0;
#ifdef LOCAL
	LOCAL_C = C;
#endif
	int dist[2] = {0};
	int cnt[2] = {0};
	while (cnt[0] < 2) {
		cnt[0] += C[dist[0]] == 0;
		dist[0]++;
	}
	while (cnt[1] < 2) {
		cnt[1] += C[N-1-dist[1]] == 0;
		dist[1]++;
	}
	//cout << dist[0] << " " << dist[1] << endl;
	send_packet(vector<bool>(N, dist[0]>dist[1]));
	vi allSafe;
	FOR(i, N) if (C[i] == 0) allSafe.push_back(i);
	vi curSafe;
	bool f = dist[0] < dist[1];
	int mIdx = f ? 0 : N-1;
	while (SZ(curSafe) < 16) {
		if (SZ(curSafe) < 2) {
			//cout << ">1<" << endl;
			bool c = C[mIdx];
			if (c == 0) curSafe.push_back(mIdx);
			send_packet(vector<bool>(N, c));
			if (f) mIdx++;
			else mIdx--;
		}
		else {
			//cout << ">2<" << endl;
			vector<bool> m(N);
			vi newSafe;
			FORR(sIdx, curSafe) {
				if ((mIdx == N && f) || (mIdx == -1 && !f)) break;
				bool c = C[mIdx];
				if (c == 0) newSafe.push_back(mIdx);
				m[sIdx] = c;
				if (f) mIdx++;
				else mIdx--;
			}
			send_packet(m);
			FORR(x, newSafe) curSafe.push_back(x);
		}
	}
	vector<bool> m(N);
	reverse(ALL(curSafe));
	FOR(i, 16) {
		m[curSafe[i]] = (SZ(M) & (1 << i)) > 0;
	}
	send_packet(m);
	int idx = 0;
	FOR(i, SZ(M)) {
		m[curSafe[idx%16]] = M[i];
		idx++;
		if (idx%16 == 0) send_packet(m);
	}
	if (idx%16 != 0) send_packet(m);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	auto getAvg = [](vector<bool> m) -> bool {
		int cnt = 0;
		FOR(i, N) cnt += m[i];
		return cnt >= 16;
	};
	bool f = getAvg(R[0]);
	vi safe;
	int idx = 1;
	vector<bool> C;
	while (SZ(safe) < 16) {
		if (f) reverse(ALL(R[idx]));
		if (SZ(safe) < 2) {
			bool c =  getAvg(R[idx]);
			if (c == 0) safe.push_back(SZ(C));
			C.push_back(c);
		}
		else {
			vi newSafe;
			FORR(s, safe) {
				if (SZ(C) == N) break;
				bool c = R[idx][s];
				if (c == 0) newSafe.push_back(SZ(C));
				C.push_back(c);
			}
			FORR(x, newSafe) safe.push_back(x);
		}
		//cout << idx << ":   "; FORR(s, safe) cout << s << " "; cout << endl;
		idx++;
	}
	C = vector<bool>(31, 1);
	FORR(s, safe) {
		if (f) s = N-1-s;
		C[s] = 0;
	}
	if (f) reverse(ALL(safe));
	//cout << "s: "; FOR(x, 16) cout << safe[x] << " "; cout << endl;
	//cout << "c: "; FOR(x, N) cout << C[x] << " "; cout << endl;

	auto read = [&](vector<bool> &m) -> vector<bool> {
		vector<bool> v;
		FOR(i, N) if (C[i] == 0) v.push_back(m[i]);
		if (!f) reverse(ALL(v));
		return v;
	};

	vector<bool> sz = read(R[idx++]);
	int n = 0;
	FOR(i, 16) n |= (1 << i) * sz[i];
	//cout << "sz: " << n << endl;
	vector<bool> ans;
	while (SZ(ans) < n) {
		//cout << "r: "; FOR(i, N) cout << R[idx][i] << " "; cout << endl;
		vector<bool> m = read(R[idx++]);
		//cout << "m: "; FOR(i, 16) cout << m[i] << " "; cout << endl;
		FOR(i, 16) {
			if (SZ(ans) == n) break;
			ans.push_back(m[i]);
		}
	}
	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: 0 / 10
• Subtask 2: 0 / 90