oj.uz

Submission #1111268

# Submission time Handle Problem Language Result Execution time Memory
1111268 2024-11-12T00:14:04 Z thieunguyenhuy Message (IOI24_message) C++17
100 / 100
 2755 ms 1112 KB 
#ifndef hwe
	#include "message.h"
#endif

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

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

#ifdef hwe
vector<bool> M, C;
vector<vector<bool>> R;

vector<bool> send_packet(vector<bool> A) {
	assert(A.size() == 31);
	for (int i = 0; i < 31; ++i) if (C[i] == 1) {
		A[i] = random(2);
	}
	R.emplace_back(A);
	return A;
}
#endif

void send_message(vector<bool> M, vector<bool> C) {
	vector<int> pos; pos.reserve(16);
	for (int i = 0; i < 31; ++i) if (!C[i]) {
		pos.emplace_back(i);
	}
	assert(pos.size() == 16);
	
	int bitM = 0;
	auto nextBit = [&]() {
		if (bitM < M.size()) return bool(M[bitM++]);
		return !M.back();
	};

	vector<vector<bool>> packets(66, vector<bool>(31, 0));
	for (int i = 0; i < 16; ++i) {
		int d = (pos[(i + 1) % 16] - pos[i] + 31) % 31;
		packets[d - 1][pos[i]] = 1;
		for (int j = d; j < 66; ++j) {
			packets[j][pos[i]] = nextBit();
		}
	}

	for (auto packet : packets) send_packet(packet);
}

vector<bool> receive_message(vector<vector<bool>> R) {
	vector<int> nxt(31, -1);
	for (int i = 0; i < 66; ++i) {
		vector<bool> packet = R[i];
		for (int j = 0; j < 31; ++j) if (packet[j] && nxt[j] == -1) {
			nxt[j] = (j + i + 1) % 31;
		}
	}

	vector<int> pos; pos.reserve(16);
	for (int i = 0; i < 31; ++i) {
		vector<bool> vis(31, false);
		int u = i, cycleSize = 0;
		while (!vis[u] && nxt[u] != -1) {
			vis[u] = true, ++cycleSize;
			u = nxt[u];
		}

		if (cycleSize == 16) {
			for (int j = 0, u = i; j < 16; ++j, u = nxt[u]) {
				pos.emplace_back(u);
			}
			break;
		}
	}

	sort (pos.begin(), pos.end()); vector<bool> M;
	for (int i = 0; i < 16; ++i) {
		int d = (pos[(i + 1) % 16] - pos[i] + 31) % 31;
		for (int j = d; j < 66; ++j) M.emplace_back(R[j][pos[i]]);
	}

	int last = M.back();
	while (M.back() == last) M.pop_back();
	return M;
}

#ifdef hwe
void solve(bool isLocal = false) {
	M.assign(1024, 0), C.assign(31, 0), R.clear();

    for (int i = 0; i < M.size(); ++i) {
    	M[i] = random(2);
    }

    vector<int> index(31); iota(index.begin(), index.end(), 0);
    shuffle(index.begin(), index.end(), rng);
    for (int i = 0; i < 15; ++i) C[index[i]] = 1;

    if (isLocal) {
    	cerr << "M = ";
    	for (auto x : M) cerr << x;
    	cerr << '\n';
    	cerr << "C = ";
    	for (auto x : C) cerr << x;
    	cerr << '\n';
    }

    send_message(M, C);
	vector<bool> ans = receive_message(R);

	if (isLocal) {
		cerr << "Ans: ";
		for (auto x : ans) cerr << x;
		cerr << '\n';
		if (ans == M) cerr << "Accepted\n";
		else {
			cerr << "Wrong Answer\n";
			exit(0);
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    for (int _ = 0; _ < 10; ++_) {
    	solve(true);
    }

    cerr << '\n'; return 0;
}
#endif

Compilation message

message.cpp: In lambda function:
message.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   if (bitM < M.size()) return bool(M[bitM++]);
      |       ~~~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 656 KB Used 66 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2685 ms 872 KB Used 66 days
2 Correct 2679 ms 864 KB Used 66 days
3 Correct 2719 ms 872 KB Used 66 days
4 Correct 2653 ms 948 KB Used 66 days
5 Correct 1944 ms 872 KB Used 66 days
6 Correct 1357 ms 1108 KB Used 66 days
7 Correct 1642 ms 944 KB Used 66 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 656 KB Used 66 days
2 Correct 2685 ms 872 KB Used 66 days
3 Correct 2679 ms 864 KB Used 66 days
4 Correct 2719 ms 872 KB Used 66 days
5 Correct 2653 ms 948 KB Used 66 days
6 Correct 1944 ms 872 KB Used 66 days
7 Correct 1357 ms 1108 KB Used 66 days
8 Correct 1642 ms 944 KB Used 66 days
9 Correct 2702 ms 876 KB Used 66 days
10 Correct 2650 ms 868 KB Used 66 days
11 Correct 2755 ms 1104 KB Used 66 days
12 Correct 2602 ms 868 KB Used 66 days
13 Correct 2641 ms 1112 KB Used 66 days
14 Correct 1913 ms 1108 KB Used 66 days
15 Correct 1395 ms 1108 KB Used 66 days
16 Correct 1888 ms 872 KB Used 66 days
17 Correct 1905 ms 872 KB Used 66 days
18 Correct 2637 ms 868 KB Used 66 days
19 Correct 2596 ms 1104 KB Used 66 days
20 Correct 2636 ms 872 KB Used 66 days
21 Correct 2658 ms 872 KB Used 66 days
22 Correct 2573 ms 1020 KB Used 66 days
23 Correct 2631 ms 872 KB Used 66 days
24 Correct 2694 ms 864 KB Used 66 days
25 Correct 2638 ms 872 KB Used 66 days
26 Correct 2645 ms 872 KB Used 66 days
27 Correct 2679 ms 1000 KB Used 66 days
28 Correct 2646 ms 872 KB Used 66 days