oj.uz

Submission #1010426

# Submission time Handle Problem Language Result Execution time Memory
1010426 2024-06-29T05:54:06 Z sleepntsheep Magic Show (APIO24_show) C++17
0 / 100
 5 ms 1320 KB 
#include <vector>
#include "Alice.h"
#include <cstdlib>

namespace {
    using u64 = unsigned long long;
    u64 coeff[5001];
    void init() {
        srand(8686);
        for (int i = 0; i < 5001; ++i) {
            coeff[i] = rand();
            coeff[i] *= rand();
            coeff[i] *= rand();
        }
    }
};


std::vector<std::pair<int,int>> Alice(){
    init();

    long long x = setN(5000);
    int i, ans;

    std::vector<std::pair<int, int > > T = { {1, 2} };

    for (i = 3; i <= 5000; ++i) {
        ans = 0;
        for (u64 j = 0; j < 60; ++j)
            ans ^= ((coeff[i] >> j) & 1) * ((x >> j) & 1);
        T.emplace_back(i, 1 + ans);
    }

    return T;
}

#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>
#include "Bob.h"
#include <cstring>


namespace {
    using u64 = unsigned long long;
    u64 coeff[5001];
    void init() {
        srand(8686);
        for (int i = 0; i < 5001; ++i) {
            coeff[i] = rand();
            coeff[i] *= rand();
            coeff[i] *= rand();
        }
    }
};


long long Bob(std::vector<std::pair<int,int>> T) {
    long long x;
    int pivot[60] = { 0 };
    int ans[5001] = { 0 };
    int used[5001] = { 0 };
    memset(ans, -1, sizeof ans);
    memset(used, 0, sizeof used);

    for (auto [u, v] : T) {
        if (u > v)
            std::swap(u, v);
        if (v <= 2)
            continue;
        ans[v] = u - 1;
    }

    init();

    for (int j = 59; j >= 0; --j) {
        int piv = -1;
        for (int i = 3; piv == -1; ++i)
            if (ans[i] != -1 && !used[i] && ((coeff[i] >> j) & 1)) {
                used[i] = 1;
                piv = i;
            }

        for (int i = 3; i <= 5000; ++i) {
            if (ans[i] == -1 || i == piv || 0 == ((coeff[i] >> j) & 1))
                continue;

            ans[i] ^= ans[piv];
            for (long long k = j; k >= 0; --k)
                coeff[i] ^= (((coeff[piv] >> k) & 1) << k);
        }
        pivot[j] = piv;
    }

    x = 0;
    for (long long j = 0; j < 60; ++j) {
        for (long long k = 0; k < 60; ++k) {
            if (k != j)
                assert(0 == ((coeff[pivot[j]] >> k) & 1));
        }
        if (ans[pivot[j]])
            x ^= 1ll << j;
    }
    return x;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1064 KB Correct.
2 Correct 5 ms 1060 KB Correct.
3 Correct 5 ms 1076 KB Correct.
4 Runtime error 5 ms 1320 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1064 KB Correct.
2 Correct 5 ms 1060 KB Correct.
3 Correct 5 ms 1076 KB Correct.
4 Runtime error 5 ms 1320 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1064 KB Correct.
2 Correct 5 ms 1060 KB Correct.
3 Correct 5 ms 1076 KB Correct.
4 Runtime error 5 ms 1320 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -