oj.uz

Submission #993134

# Submission time Handle Problem Language Result Execution time Memory
993134 2024-06-05T10:55:13 Z boris_mihov Magic Show (APIO24_show) C++17
0 / 100
 1 ms 344 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::fill(isGood, isGood + MAXN, 0);
        std::fill(renum, renum + MAXN, 0);
        for (int lg = 1 ; lg <= 11 ; ++lg)
        {
            for (int num = (1 << lg) ; num < (1 << lg) + (1 << lg - 1) ; ++num)
            {
                isGood[num] = true;
                renum[num] = bit++;
                if (bit == 60) bit = 0;
            }
        }
    }
}

std::vector<std::pair<int,int>> Alice()
{
    calcIsGood();
    llong x = setN(4095);
    std::cout << "x is: " << x << '\n';
    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)) == 0)
                {
                    edges.push_back({u, nextLevelEven.back()});
                    nextLevelEven.pop_back();

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

                    edges.push_back({u, nextLevelOdd.back()});
                    nextLevelOdd.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::fill(isGood, isGood + MAXN, 0);
        std::fill(renum, renum + MAXN, 0);
        for (int lg = 1 ; lg <= 11 ; ++lg)
        {
            for (int num = (1 << lg) ; num < (1 << lg) + (1 << lg - 1) ; ++num)
            {
                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:24:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |             for (int num = (1 << lg) ; num < (1 << lg) + (1 << lg - 1) ; ++num)
      |                                                                ~~~^~~
Alice.cpp: In function 'std::vector<std::pair<int, int> > Alice()':
Alice.cpp:47:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   47 |         for (int i = (1 << lg) ; i < (1 << lg + 1) ; ++i)
      |                                            ~~~^~~
Alice.cpp:77:59: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   77 |                 if ((((u & 1) ^ ((x & (1LL << renum[u]))) > 0)) == 0)
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -