Submission #1067026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067026		myst6	Ancient Machine 2 (JOI23_ancient2)	C++17	99 / 100	48 ms	1320 KiB

ancient2

#include "ancient2.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_BITS = 1000;
const int BOUND = 53;
const int MAX_M = BOUND * 2;

#define bs bitset<MAX_BITS>

vector<pair<bs,array<int,3>>> MIS(const vector<pair<bs,array<int,3>>>& vectors) {
    vector<bs> basis;  // Store the basis vectors here
    vector<pair<bs,array<int,3>>> mis;

    for (const auto& vec : vectors) {
        bs v = vec.first;  // Copy the vector

        // Try to eliminate the current vector with the basis vectors
        for (const auto& b : basis) {
            if (v.none()) break;  // If the vector is already zero, skip
            if (v.test(b._Find_first())) {  // If leading bit matches
                v ^= b;  // Subtract the basis vector (add in GF(2))
            }
        }

        // If the vector is not zero after elimination, it's linearly independent
        if (v.any()) {
            basis.push_back(v);
            mis.push_back(vec);  // Add the original vector to the mis 
        }
    }

    return mis;
}

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];
                }
            }
        }
    }
}

string solve(int N, vector<pair<bs,int>> &info) {
    // Create bitsets
    vector<bs> A(N);
    bs S, b;

    // Populate the matrix A and vector b with parity information
    for (int i=0; i<N; i++) {
        A[i] = info[i].first;
        b[i] = info[i].second;
    }

    // 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);
}

string Solve(int N) {
    vector<pair<bs,int>> info;
    function<int(int,int)> solve1 = [&](int i, int j) -> int {
        int m = 2 * j;
        vector<int> a(m), b(m);
        for (int r=0; r<j; r++) {
            a[r] = (r + 1) % j;
            b[r] = (r + 1) % j;
            a[j + r] = j + ((r + 1) % j);
            b[j + r] = j + ((r + 1) % j);
        }
        swap(b[i], b[i + j]);
        return Query(m, a, b) / j;
    }; 
    function<int(int)> solve2 = [&](int k) -> int {
        int m = k + 3;
        vector<int> a(m), b(m);
        for (int r=0; r<k; r++) {
            a[r] = r + 1;
            b[r] = r + 1;
        }
        a[k] = k + 1;
        b[k] = k + 2;
        a[k + 1] = b[k + 1] = k + 1;
        a[k + 2] = b[k + 2] = k + 2;
        return Query(m, a, b) - k - 1;
    };
    function<int(string)> solve3 = [&](string end) -> int {
        end = "1" + end;
        int k = end.size();
        int m = k + 1;
        vector<int> a(m), b(m);
        for (int r=0; r<=k; r++) {
            string curr = end.substr(0, r);
            function<int(int)> go = [&](char ch) -> int {
                string next = curr + ch;
                int k = next.size();
                for (int i=k; i>0; i--) {
                    if (next.substr(k - i, i) == end.substr(0, i)) {
                        return i;
                    }
                }
                return 0;
            };
            a[r] = go('0');
            b[r] = go('1');
        }
        return Query(m, a, b) == k;
    };
    vector<pair<bs,array<int,3>>> all;
    for (int i=0; i<=min(MAX_M-3,N); i++) {
        bs here;
        here[i] = 1;
        all.push_back({here, {1, i, i}});
    }
    string end;
    for (int i=0; i<=min(MAX_M-3,N-1); i++) {
        bs here;
        here[N - 1 - i] = 1;
        end = string(1, '0' + solve3(end)) + end;
        all.push_back({here, {2, i, i}});
    }
    for (int j=1; j<=BOUND; j++) {
        for (int i=0; i<j; i++) {
            bs here;
            for (int k=i; k<N; k+=j) {
                here[k] = 1;
            }
            all.push_back({here, {0, i, j}});
        }
    }
    vector<pair<bs,array<int,3>>> mis = MIS(all);
    for (auto &[HELP, bruh] : mis) {
        if (info.size() == N) {
            break;
        } else if (bruh[0] == 0) {
            info.push_back({HELP, solve1(bruh[1], bruh[2])});
        } else if (bruh[0] == 1) {
            info.push_back({HELP, solve2(bruh[1])});
        } else if (bruh[0] == 2) {
            info.push_back({HELP, end[(int) end.size() - 1 - bruh[1]] - '0'});
        } else {
            assert(false);
        }
    }
    // assert(info.size() >= N);
    // cout << 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:179:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::bitset<1000>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |         if (info.size() == N) {
      |             ~~~~~~~~~~~~^~~~

• Subtask 1: 99 / 100