Submission #1066423

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1066423	2024-08-19T21:18:53 Z	myst6	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	2000 ms	344 KB

ancient2

#include "ancient2.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_BITS = 1000;

vector<bitset<MAX_BITS>> A(MAX_BITS);
bitset<MAX_BITS> S;
bitset<MAX_BITS> b;

void gaussian_elimination() {
    int row = 0;

    for (int col = 0; col < MAX_BITS; ++col) {
        // Find pivot row
        int pivot = -1;
        for (int i = row; i < MAX_BITS; ++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 < MAX_BITS; ++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 < MAX_BITS; ++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(vector<array<int,3>> &info) {
    // 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 < MAX_BITS; k += j) {
            A[equation_index][k] = 1;
        }
        b[equation_index] = parity /* Your parity information for p_{i,j} */;
        equation_index++;
    }
    assert(equation_index == MAX_BITS);

    // Perform Gaussian elimination
    gaussian_elimination();

    // Output the reconstructed binary string
    return S.to_string();
}

string Solve(int N) {
    vector<array<int,3>> info(MAX_BITS);
    for (int j=1; ; j++) {
        for (int i=1; i<j; 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)});
            if (info.size() == MAX_BITS) break;
        }
        if (info.size() == MAX_BITS) break;
    }

    return solve(info);
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3062 ms	344 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-