Submission #993146

#	Time	Username	Problem	Language	Result	Execution time	Memory
993146		boris_mihov	Magic Show (APIO24_show)	C++17	100 / 100	2 ms	1080 KiB

Alice

#include "Alice.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <vector>

typedef long long llong;
namespace
{
    const int MAXN = 1 << 12;
    bool isGood[MAXN];
    int renum[MAXN];

    void calcIsGood()
    {
        int bit = 0;
        std::mt19937 rng(69420);
        std::fill(isGood, isGood + MAXN, 0);
        std::fill(renum, renum + MAXN, 0);
        for (int lg = 1 ; lg <= 11 ; ++lg)
        {
            std::vector <int> nodes;
            for (int num = (1 << lg) ; num < (1 << lg + 1) ; ++num)
            {
                nodes.push_back(num);
            }

            for (int pos = 0 ; pos < (1 << lg - 1) ; ++pos)
            {
                int num = nodes[pos];
                isGood[num] = true;
                renum[num] = bit++;
                if (bit == 60) bit = 0;
            }
        }
    }
}

std::vector<std::pair<int,int>> Alice()
{
    calcIsGood();
    llong x = setN(4095);
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    std::vector <std::pair <int,int>> edges;
    for (int lg = 0 ; lg <= 10 ; ++lg)
    {
        std::vector <int> currentLevel;
        std::vector <int> nextLevelOdd;
        std::vector <int> nextLevelEven;

        for (int i = (1 << lg) ; i < (1 << lg + 1) ; ++i)
        {
            currentLevel.push_back(i);
            nextLevelEven.push_back(2 * i);
            nextLevelOdd.push_back(2 * i + 1);
        }

        std::shuffle(nextLevelOdd.begin(), nextLevelOdd.end(), rng);
        std::shuffle(nextLevelEven.begin(), nextLevelEven.end(), rng);

        for (const int &u : currentLevel)
        {
            if (!isGood[u])
            {
                int cnt = 0;
                while (nextLevelOdd.size() && cnt < 2)
                {
                    edges.push_back({u, nextLevelOdd.back()});
                    nextLevelOdd.pop_back();
                    cnt++;
                }

                while (nextLevelEven.size() && cnt < 2)
                {
                    edges.push_back({u, nextLevelEven.back()});
                    nextLevelEven.pop_back();
                    cnt++;
                }
            } else
            {
                if (((u & 1) ^ ((x & (1LL << renum[u]))) > 0))
                {
                    edges.push_back({u, nextLevelOdd.back()});
                    nextLevelOdd.pop_back();

                    edges.push_back({u, nextLevelOdd.back()});
                    nextLevelOdd.pop_back();
                    
                } else
                {
                    edges.push_back({u, nextLevelEven.back()});
                    nextLevelEven.pop_back();

                    edges.push_back({u, nextLevelEven.back()});
                    nextLevelEven.pop_back();
                }
            }
        }
    }

    return edges;
}

Bob

#include "Alice.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <vector>

typedef long long llong;
namespace
{
    const int MAXN = 1 << 12;
    bool isGood[MAXN];
    int renum[MAXN];

    void calcIsGood()
    {
        int bit = 0;
        std::mt19937 rng(69420);
        std::fill(isGood, isGood + MAXN, 0);
        std::fill(renum, renum + MAXN, 0);
        for (int lg = 1 ; lg <= 11 ; ++lg)
        {
            std::vector <int> nodes;
            for (int num = (1 << lg) ; num < (1 << lg + 1) ; ++num)
            {
                nodes.push_back(num);
            }

            for (int pos = 0 ; pos < (1 << lg - 1) ; ++pos)
            {
                int num = nodes[pos];
                isGood[num] = true;
                renum[num] = bit++;
                if (bit == 60) bit = 0;
            }
        }
    }
}

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

bool foundBit[60];
long long Bob(std::vector <std::pair<int,int>> edges)
{
    calcIsGood();
    std::vector <int> children[MAXN];
    llong answer = 0;
    for (auto &[u, v] : edges)
    { 
        if (isGood[u])
        {
            // std::cout << "Good: " << u << ' ' << renum[u] << '\n';
            foundBit[renum[u]] = true;
            answer |= (1LL << renum[u]) * ((u ^ v) & 1);
        }
    }

    // exit(0);
    for (int i = 0 ; i < 60 ; ++i)
    {
        assert(foundBit[i]);
    }

    return answer;
}

Compilation message (stderr)

Alice.cpp: In function 'void {anonymous}::calcIsGood()':
Alice.cpp:26:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   26 |             for (int num = (1 << lg) ; num < (1 << lg + 1) ; ++num)
      |                                                    ~~~^~~
Alice.cpp:31:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |             for (int pos = 0 ; pos < (1 << lg - 1) ; ++pos)
      |                                            ~~~^~~
Alice.cpp: In function 'std::vector<std::pair<int, int> > Alice()':
Alice.cpp:54:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   54 |         for (int i = (1 << lg) ; i < (1 << lg + 1) ; ++i)
      |                                            ~~~^~~
Alice.cpp:84:58: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   84 |                 if (((u & 1) ^ ((x & (1LL << renum[u]))) > 0))
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Bob.cpp: In function 'void {anonymous}::calcIsGood()':
Bob.cpp:26:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   26 |             for (int num = (1 << lg) ; num < (1 << lg + 1) ; ++num)
      |                                                    ~~~^~~
Bob.cpp:31:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |             for (int pos = 0 ; pos < (1 << lg - 1) ; ++pos)
      |                                            ~~~^~~

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