Submission #1186402

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

Alice

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

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

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

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

    long long x = setN (n);

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

        /*
    for (auto i: arr) cout << i << ' ';
    cout << endl;
    */

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

        /*
    for (auto i: arr) cout << i << ' ';
    cout << endl;
    */

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

	return tree_trans;
}

Bob

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

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

int 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 (14092007);
    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), 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 ++]] --;
        }
    }

    for (int i = 0; i < lgn; i ++)
        assert (vote[i] > 0);

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

    return ans;
}

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