oj.uz

Submission #993146

# Submission time Handle Problem Language Result Execution time Memory
993146 2024-06-05T11:02:13 Z boris_mihov Magic Show (APIO24_show) C++17
100 / 100
 2 ms 1080 KB 
#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;
}

#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Correct.
2 Correct 1 ms 812 KB Correct.
3 Correct 1 ms 812 KB Correct.
4 Correct 2 ms 812 KB Correct.
5 Correct 1 ms 812 KB Correct.
6 Correct 2 ms 812 KB Correct.
7 Correct 1 ms 1024 KB Correct.
8 Correct 1 ms 812 KB Correct.
9 Correct 1 ms 808 KB Correct.
10 Correct 2 ms 1068 KB Correct.
11 Correct 2 ms 812 KB Correct.
12 Correct 1 ms 812 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Correct.
2 Correct 1 ms 812 KB Correct.
3 Correct 1 ms 812 KB Correct.
4 Correct 2 ms 812 KB Correct.
5 Correct 1 ms 812 KB Correct.
6 Correct 2 ms 812 KB Correct.
7 Correct 1 ms 1024 KB Correct.
8 Correct 1 ms 812 KB Correct.
9 Correct 1 ms 808 KB Correct.
10 Correct 2 ms 1068 KB Correct.
11 Correct 2 ms 812 KB Correct.
12 Correct 1 ms 812 KB Correct.
13 Correct 1 ms 1068 KB Correct.
14 Correct 2 ms 1080 KB Correct.
15 Correct 2 ms 1076 KB Correct.
16 Correct 1 ms 812 KB Correct.
17 Correct 2 ms 812 KB Correct.
18 Correct 1 ms 816 KB Correct.
19 Correct 2 ms 920 KB Correct.
20 Correct 2 ms 1076 KB Correct.
21 Correct 2 ms 1068 KB Correct.
22 Correct 2 ms 812 KB Correct.
23 Correct 1 ms 812 KB Correct.
24 Correct 1 ms 812 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Correct.
2 Correct 1 ms 812 KB Correct.
3 Correct 1 ms 812 KB Correct.
4 Correct 2 ms 812 KB Correct.
5 Correct 1 ms 812 KB Correct.
6 Correct 2 ms 812 KB Correct.
7 Correct 1 ms 1024 KB Correct.
8 Correct 1 ms 812 KB Correct.
9 Correct 1 ms 808 KB Correct.
10 Correct 2 ms 1068 KB Correct.
11 Correct 2 ms 812 KB Correct.
12 Correct 1 ms 812 KB Correct.
13 Correct 1 ms 1068 KB Correct.
14 Correct 2 ms 1080 KB Correct.
15 Correct 2 ms 1076 KB Correct.
16 Correct 1 ms 812 KB Correct.
17 Correct 2 ms 812 KB Correct.
18 Correct 1 ms 816 KB Correct.
19 Correct 2 ms 920 KB Correct.
20 Correct 2 ms 1076 KB Correct.
21 Correct 2 ms 1068 KB Correct.
22 Correct 2 ms 812 KB Correct.
23 Correct 1 ms 812 KB Correct.
24 Correct 1 ms 812 KB Correct.
25 Correct 2 ms 1068 KB Correct.
26 Correct 2 ms 1064 KB Correct.
27 Correct 2 ms 1068 KB Correct.
28 Correct 1 ms 1068 KB Correct.
29 Correct 1 ms 1076 KB Correct.
30 Correct 2 ms 820 KB Correct.
31 Correct 1 ms 812 KB Correct.
32 Correct 1 ms 812 KB Correct.
33 Correct 1 ms 820 KB Correct.
34 Correct 2 ms 812 KB Correct.
35 Correct 2 ms 1076 KB Correct.
36 Correct 1 ms 820 KB Correct.
37 Correct 2 ms 812 KB Correct.
38 Correct 2 ms 1080 KB Correct.
39 Correct 2 ms 1068 KB Correct.
40 Correct 2 ms 808 KB Correct.
41 Correct 2 ms 812 KB Correct.
42 Correct 2 ms 820 KB Correct.
43 Correct 1 ms 820 KB Correct.
44 Correct 1 ms 816 KB Correct.