Submission #1066457

#TimeUsernameProblemLanguageResultExecution timeMemory
1066457myst6Ancient Machine 2 (JOI23_ancient2)C++17
82 / 100
36 ms720 KiB
#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++; } // 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); } /* if i have all of modulo j then take any factor, and it's already covered so i have to choose only prime j */ vector<int> primes = { 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 }; string Solve(int N) { vector<array<int,3>> info; for (int j : primes) { for (int i=0; i<j-1; i++) { 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}); if (info.size() == N) break; } if (info.size() == N) break; } assert(info.size() == N); // cout << solve(N, info) << "\n"; return solve(N, info); }

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:118: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]
  118 |             if (info.size() == N) break;
      |                 ~~~~~~~~~~~~^~~~
ancient2.cpp:120: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]
  120 |         if (info.size() == N) break;
      |             ~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ancient2.cpp:3:
ancient2.cpp:122:24: 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 |     assert(info.size() == N);
      |            ~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...