Submission #1186432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186432		sqrtxsunlight	Magic Show (APIO24_show)	C++17	100 / 100	6 ms	632 KiB

Alice

#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;

int n = 5000, cnt_trans = 0, lgn = 61;

long long Rand (int l, int r)
{
    unsigned long long x = (rand () << 15) ^ rand ();
    return x % (r - l + 1) + l;
}

int log2 (int i)
{
    int ans = 0;
    while (i) i /= 2, ans ++;
    return (-- ans);
}

vector <pair <int, int>> Alice()
{
    srand (24022007);
    long long magic = 0;
    for (int i = 0; i < lgn - 1; i ++)
        magic ^= (Rand (0, 1) << i);
    cerr << magic << '\n';

    vector <pair <int, int>> tree_trans;
    for (int i = 1; i <= n; i ++)
        cnt_trans += log2 (i - 1);

    long long x = setN (n);
    x ^= magic;

    long long bit61 = 0;
    for (int i = 0; i < lgn - 1; i ++)
        bit61 ^= ((x & (1LL << i)) > 0);

    x ^= (bit61 << 61);

    vector <int> arr (cnt_trans, 0);
    for (int i = 0; i < cnt_trans; i ++)
        arr[i] = i % lgn;

    for (int i = 0; i < cnt_trans; i ++)
        swap (arr[i], arr[Rand (0, i)]);

    string trans;
    int cur_pos = 0;
    for (int i = 2; i <= n; i ++)
    {
        int lg = floor (log2 (i - 1)), p = 0;
        for (int j = 0; j < lg; j ++)
            p += (((x & (1LL << arr[cur_pos ++])) > 0) << j);
        p ++;
        tree_trans.push_back (make_pair (p, i));
    }

	return tree_trans;
}

Bob

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;

#ifndef TKML
int n = 5000, cnt_trans = 0, lgn = 61;

long long Rand (int l, int r)
{
    unsigned long long x = (rand () << 15) ^ rand ();
    return x % (r - l + 1) + l;
}

int log2 (int i)
{
    int ans = 0;
    while (i) i /= 2, ans ++;
    return (-- ans);
}
#endif // TKML

long long Bob (vector <pair <int, int>> tree)
{
    srand (24022007);
    long long magic = 0;
    for (int i = 0; i < lgn - 1; i ++)
        magic ^= (Rand (0, 1) << i);
    cerr << magic << '\n';

    for (int i = 1; i <= n; i ++)
        cnt_trans += log2 (i);

    vector <int> par (n + 1, -1);
    for (auto i: tree) par[i.second] = i.first;

    vector <int> arr (cnt_trans, 0);
    for (int i = 0; i < cnt_trans; i ++)
        arr[i] = i % lgn;

    for (int i = 0; i < cnt_trans; i ++)
        swap (arr[i], arr[Rand (0, i)]);

    vector <int> vote (lgn, 0);

    int cur_pos = 0;
    long long ans = 0;
    for (int i = 2; i <= n; i ++)
    {
        int lg = log2 (i - 1), p = 0;
        if (par[i] > 0) par[i] --;
        for (int j = 0; j < lg; j ++)
        {
            if (par[i] == -1)
            {
                cur_pos ++;
                continue;
            }
            if (par[i] & (1 << j))
                vote[arr[cur_pos ++]] ++;
            else vote[arr[cur_pos ++]] --;
        }
    }

    int cnt = 0;
    for (int i = 0; i < lgn; i ++)
        if (vote[i] == 0) cnt ++;

    assert (cnt <= 1);

    for (int i = 0; i < lgn; i ++)
        if (vote[i] > 0) ans |= (1LL << i);

    if (vote[lgn - 1] == 0) return (ans ^ magic);

    long long bit61 = (ans & (1LL << lgn));
    ans ^= bit61;
    bit61 >>= lgn;

    for (int i = 0; i < lgn - 1; i ++)
        bit61 ^= ((ans & (1LL << i)) > 0);

    if (bit61)
        for (int i = 0; i < lgn - 1; i ++)
            if (vote[i] == 0) ans |= (1LL << i);

    return (ans ^ magic);
}

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