oj.uz

Submission #1067027

# Submission time Handle Problem Language Result Execution time Memory
1067027 2024-08-20T09:53:36 Z myst6 Ancient Machine 2 (JOI23_ancient2) C++17
100 / 100
 57 ms 1468 KB 
#include "ancient2.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_BITS = 1000;
const int BOUND = 51;
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

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 964 KB Output is correct
2 Correct 47 ms 1132 KB Output is correct
3 Correct 33 ms 1032 KB Output is correct
4 Correct 33 ms 964 KB Output is correct
5 Correct 48 ms 1096 KB Output is correct
6 Correct 41 ms 1200 KB Output is correct
7 Correct 43 ms 1312 KB Output is correct
8 Correct 36 ms 964 KB Output is correct
9 Correct 41 ms 964 KB Output is correct
10 Correct 37 ms 1228 KB Output is correct
11 Correct 35 ms 1060 KB Output is correct
12 Correct 42 ms 1020 KB Output is correct
13 Correct 33 ms 964 KB Output is correct
14 Correct 33 ms 1044 KB Output is correct
15 Correct 33 ms 1212 KB Output is correct
16 Correct 34 ms 1216 KB Output is correct
17 Correct 43 ms 964 KB Output is correct
18 Correct 37 ms 1028 KB Output is correct
19 Correct 34 ms 964 KB Output is correct
20 Correct 36 ms 1068 KB Output is correct
21 Correct 35 ms 964 KB Output is correct
22 Correct 48 ms 964 KB Output is correct
23 Correct 33 ms 1028 KB Output is correct
24 Correct 39 ms 964 KB Output is correct
25 Correct 47 ms 1160 KB Output is correct
26 Correct 37 ms 1196 KB Output is correct
27 Correct 38 ms 1304 KB Output is correct
28 Correct 38 ms 988 KB Output is correct
29 Correct 33 ms 1036 KB Output is correct
30 Correct 35 ms 1388 KB Output is correct
31 Correct 50 ms 1200 KB Output is correct
32 Correct 39 ms 1468 KB Output is correct
33 Correct 36 ms 1140 KB Output is correct
34 Correct 34 ms 964 KB Output is correct
35 Correct 34 ms 1316 KB Output is correct
36 Correct 33 ms 964 KB Output is correct
37 Correct 35 ms 1396 KB Output is correct
38 Correct 37 ms 1236 KB Output is correct
39 Correct 36 ms 1028 KB Output is correct
40 Correct 36 ms 964 KB Output is correct
41 Correct 34 ms 1008 KB Output is correct
42 Correct 38 ms 996 KB Output is correct
43 Correct 35 ms 1032 KB Output is correct
44 Correct 43 ms 1148 KB Output is correct
45 Correct 38 ms 1184 KB Output is correct
46 Correct 41 ms 1024 KB Output is correct
47 Correct 42 ms 956 KB Output is correct
48 Correct 38 ms 1020 KB Output is correct
49 Correct 43 ms 1036 KB Output is correct
50 Correct 39 ms 1032 KB Output is correct
51 Correct 36 ms 964 KB Output is correct
52 Correct 36 ms 1140 KB Output is correct
53 Correct 38 ms 1172 KB Output is correct
54 Correct 34 ms 1132 KB Output is correct
55 Correct 43 ms 964 KB Output is correct
56 Correct 35 ms 964 KB Output is correct
57 Correct 33 ms 1040 KB Output is correct
58 Correct 57 ms 964 KB Output is correct
59 Correct 32 ms 1040 KB Output is correct
60 Correct 34 ms 964 KB Output is correct
61 Correct 51 ms 1208 KB Output is correct
62 Correct 35 ms 1140 KB Output is correct
63 Correct 56 ms 1040 KB Output is correct