Submission #1066512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066512		myst6	Ancient Machine 2 (JOI23_ancient2)	C++17	89 / 100	35 ms	944 KiB

ancient2

#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 = 79;

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;
        int p = j;
        // while (j * p <= BOUND) j *= p;
        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-q; i++) {
                if (info.size() == N) break;
                if (i > q) {
                    add(i, j);
                }
            }
        }
    }
    // cout << info.size() << "\n";
    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: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:119: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]
  119 |             if (info.size() == N) break;
      |                 ~~~~~~~~~~~~^~~~
ancient2.cpp:116:13: warning: unused variable 'p' [-Wunused-variable]
  116 |         int p = j;
      |             ^
ancient2.cpp:124: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]
  124 |         if (info.size() == N) break;
      |             ~~~~~~~~~~~~^~~~
ancient2.cpp:126: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]
  126 |             if (info.size() == N) break;
      |                 ~~~~~~~~~~~~^~~~
ancient2.cpp:131: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]
  131 |                 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:139: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]
  139 |     assert(info.size() >= N);
      |            ~~~~~~~~~~~~^~~~

• Subtask 1: 89 / 100