#include "ancient2.h"
#include <iostream>
#include <bitset>
#include <cassert>
#include <memory>
#include <numeric>
#include <string>
#include <vector>
void gauss(std::bitset<1001> (&matrix)[1000]) {
for (int col = 0; col < 1000; col++) {
int pivot_row;
for (int row = col; row < 1000; row++) {
if (matrix[row][col]) {
pivot_row = row;
break;
}
}
std::swap(matrix[col], matrix[pivot_row]);
for (int row = col + 1; row < 1000; row++)
if (matrix[row][col])
matrix[row] ^= matrix[col];
}
for (int col = 999; col >= 0; col--)
for (int row = col - 1; row >= 0; row--)
if (matrix[row][col])
matrix[row] ^= matrix[col];
}
std::string Solve(int N) {
constexpr int W = 56;
int m = W * 2;
std::vector<int> a(m), b(m);
std::vector<bool> results;
int acc_phi = 0;
auto matrix = std::make_unique<std::bitset<1001>[]>(1000);
auto init_cyclic = [&](int i) -> void {
for (int j = 0; j < i; j++) {
a[j] = j + 1;
a[j + i] = j + i + 1;
b[j] = j + 1;
b[j + i] = j + i + 1;
}
a[i - 1] = 0;
a[i - 1 + i] = i;
b[i - 1] = 0;
b[i - 1 + i] = i;
};
int cur = 0;
for (int i = 1; i <= W; i++) {
init_cyclic(i);
int phi = 0;
for (int j = 1; j <= i; j++)
if (std::gcd(i, j) == 1)
phi += 1;
for (int j = 0; j < phi; j++) {
// std::cout << "making matrix for " << i << ' ' << j << '\n';
for (int k = 0; k < 1000; k++) {
// std::cout << k << ": " << (k % i == j) << '\n';
if (k % i == j) {
matrix[cur][k] = 1;
}
}
std::swap(b[j], b[j + i]);
matrix[cur++][1000] = Query(m, a, b) >= i;
std::swap(b[j], b[j + i]);
}
}
init_cyclic(W);
for (int pos = 999; cur < 1000; pos--) {
matrix[cur][pos] = 1;
auto i = pos % W;
std::swap(a[W + i], b[i]);
matrix[cur++][1000] = Query(m, a, b) >= W;
std::swap(a[W + i], b[i]);
}
gauss(*(std::bitset<1001>(*)[1000])matrix.get());
std::string s;
for (int i = 0; i < N; i++)
s.push_back(matrix[i][1000] ? '1' : '0');
std::cout << s << '\n';
return s;
}
Compilation message
ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:37:7: warning: unused variable 'acc_phi' [-Wunused-variable]
37 | int acc_phi = 0;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
592 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
