#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_BITS = 1000;
#define bs bitset<MAX_BITS>
void gaussian_elimination(vector<bs> &A, bs &S, bs &b, int N) {
int row = 0;
for (int col = 0; col < N; ++col) {
// Find pivot row
int pivot = -1;
for (int i = row; i < N; ++i) {
if (A[i][col]) {
pivot = i;
break;
}
}
if (pivot == -1) continue; // No pivot found, move to the next column
// Swap pivot row with the current row
swap(A[row], A[pivot]);
// swap(b[row], b[pivot]);
int tmp = b[row];
b[row] = b[pivot];
b[pivot] = tmp;
// Eliminate below
for (int i = row + 1; i < N; ++i) {
if (A[i][col]) {
A[i] ^= A[row];
// b[i] ^= b[row];
if (b[row]) b[i] = !b[i];
}
}
++row;
}
// Backward substitution
S.reset();
for (int i = row - 1; i >= 0; --i) {
if (A[i].any()) {
int leading_one = A[i]._Find_first();
S[leading_one] = b[i];
for (int j = leading_one + 1; j < N; ++j) {
if (A[i][j]) {
// S[leading_one] ^= S[j];
if (S[j]) S[leading_one] = !S[leading_one];
}
}
}
}
}
// info[m][r] => index === r (mod m)
string solve(int N, vector<array<int,3>> &info) {
// Clear old stuff
vector<bs> A(N);
bs S, b;
// Populate the matrix A and vector b with parity information
int equation_index = 0;
for (auto [i, j, parity] : info) {
for (int k = i; k < N; k += j) {
A[equation_index][k] = 1;
}
// cerr << i << "," << j << "," << parity << "\n";
b[equation_index] = parity /* Your parity information for p_{i,j} */;
equation_index++;
if (equation_index == N) break;
}
// Perform Gaussian elimination
gaussian_elimination(A, S, b, N);
// Output the reconstructed binary string
string s = S.to_string();
reverse(s.begin(), s.end());
return s.substr(0, N);
}
const int BOUND = 80;
vector<int> P = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
151, 157, 163
};
string Solve(int N) {
vector<array<int,3>> info;
function<void(int,int)> add = [&](int i, int j) -> void {
int m = 2 * j;
vector<int> a(m), b(m);
// nodes r=0..j-1 is even parity modulo r
// nodes r=j..2j-1 is odd parity modulo r
for (int r=0; r<j; r++) {
// both transition to next node in chain
a[r] = (r + 1) % j;
b[r] = (r + 1) % j;
a[j + r] = j + ((r + 1) % j);
b[j + r] = j + ((r + 1) % j);
}
// if one, transition to opposite node in chain
b[i] = j + ((i + 1) % j);
b[i + j] = (i + 1) % j;
info.push_back({i, j, Query(m, a, b) / j});
};
for (int j : P) {
if (info.size() == N) break;
if (j > BOUND) continue;
for (int i=0; i<j-1; i++) {
if (info.size() == N) break;
add(i, j);
}
}
for (int p : P) {
if (info.size() == N) break;
for (int q : P) {
if (info.size() == N) break;
if (p >= q) continue;
int j = p * q;
if (j > BOUND) continue;
for (int i=0; i<j-1; i++) {
if (info.size() == N) break;
if (i >= max(p, q)) {
// cout << i << "," << j << "\n";
add(i, j);
}
}
}
}
// cout << info.size() << "\n";
// assert(info.size() >= N);
// cout << solve(N, info) << "\n";
return solve(N, info);
}
Compilation message
ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:114:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (info.size() == N) break;
| ~~~~~~~~~~~~^~~~
ancient2.cpp:117:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
117 | if (info.size() == N) break;
| ~~~~~~~~~~~~^~~~
ancient2.cpp:122:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
122 | if (info.size() == N) break;
| ~~~~~~~~~~~~^~~~
ancient2.cpp:124:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
124 | if (info.size() == N) break;
| ~~~~~~~~~~~~^~~~
ancient2.cpp:129:33: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
129 | if (info.size() == N) break;
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
21 ms |
468 KB |
Output is partially correct |
| 2 |
Incorrect |
32 ms |
456 KB |
Wrong Answer [3] |
| 3 |
Halted |
0 ms |
0 KB |
- |
