Submission #1010454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010454		sleepntsheep	Magic Show (APIO24_show)	C++17	0 / 100	1097 ms	21048 KiB

Alice

#include <vector>
#include <random>
#include "Alice.h"

namespace {
    long long coeff[5001];
    void init() {
        std::mt19937 gen(86866);
        std::uniform_int_distribution<long long> dis(0, (1ll << 60) - 1);
        for (int i = 0; i < 5001; ++i)
            coeff[i] = dis(gen);
    }
};


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 (long long j = 0; j < 60; ++j)
            ans ^= ((coeff[i] >> j) & 1) * ((x >> j) & 1);
        T.emplace_back(i, 1 + ans);
    }

    return T;
}

Bob

#include <vector>
#include <sys/time.h>
#include <algorithm>
#include "Bob.h"
#include <cstring>
#include <random>


namespace {
    long long coeff[5001];
    void init() {
        std::mt19937 gen(86866);
        std::uniform_int_distribution<long long> dis(0, (1ll << 60) - 1);
        for (int i = 0; i < 5001; ++i)
            coeff[i] = dis(gen);
    }
};


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();


    struct timeval time; 
    gettimeofday(&time,NULL);
    std::mt19937 gen((time.tv_sec * 1000) + (time.tv_usec / 1000));

    for (int j = 59; j >= 0; --j) {
        int piv = -1;
        std::vector<int> ok;
        for (int i = 3; i <= 5000; ++i)
            if (ans[i] != -1 && !used[i] && ((coeff[i] >> j) & 1))
                ok.push_back(i);
        if (ok.empty())return Bob(T);
        std::uniform_int_distribution<long long> dis(0, ok.size() - 1);
        piv = ok[dis(gen)];
        used[piv] = 1;

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

            ans[i] ^= ans[piv];
            coeff[i] ^= coeff[piv];
        }

        pivot[j] = piv;
    }

    x = 0;
    for (long long j = 0; j < 60; ++j)
        x ^= ans[pivot[j]] << j;
    return x;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65