oj.uz

Submission #908641

# Submission time Handle Problem Language Result Execution time Memory
908641 2024-01-16T15:45:40 Z GrandTiger1729 Flight to the Ford (BOI22_communication) C++17
74 / 100
 2285 ms 3568 KB 
#include "communication.h"
#include <bits/stdc++.h>
using namespace std;

void encode(int N, int X)
{
    int ans = 0;
    vector<int> res[2];
    int x = 0;
    res[0].push_back(0);
    for (int y = 1; y <= 29; y++)
    {
        if (1 << y > N)
        {
            break;
        }
        int re[4]{};
        re[0] = send(X >> x & 1);
        re[1] = send(X >> y & 1);
        re[2] = send(X >> y & 1);
        if (re[1] == re[2])
        {
            ans ^= re[1] << y;
            continue;
        }
        re[3] = send(X >> x & 1);
        if (re[0] == re[3])
        {
            for (auto &i : res[0])
            {
                ans ^= re[0] << i;
            }
            for (auto &i : res[1])
            {
                ans ^= (!re[0]) << i;
            }
            res[0] = res[1] = vector<int>();
            res[0].push_back(y);
            x = y;
        }
        else
        {
            res[re[0] ^ re[1] ^ 1].push_back(y);
        }
    }
}

pair<int, int> decode(int N)
{
    int ans = 0;
    vector<int> res[2];
    int x = 0;
    res[0].push_back(0);
    for (int y = 1; y <= 29; y++)
    {
        if (1 << y > N)
        {
            break;
        }
        int re[4]{};
        re[0] = receive();
        re[1] = receive();
        re[2] = receive();
        if (re[1] == re[2])
        {
            ans ^= re[1] << y;
            continue;
        }
        re[3] = receive();
        if (re[0] == re[3])
        {
            for (auto &i : res[0])
            {
                ans ^= re[0] << i;
            }
            for (auto &i : res[1])
            {
                ans ^= (!re[0]) << i;
            }
            res[0] = res[1] = vector<int>();
            res[0].push_back(y);
            x = y;
        }
        else
        {
            res[re[0] ^ re[1] ^ 1].push_back(y);
        }
    }
    int ans1 = ans, ans2 = ans;
    for (auto &i : res[0])
    {
        ans1 ^= 1 << i;
    }
    for (auto &i : res[1])
    {
        ans2 ^= 1 << i;
    }
    ans1 = clamp(ans1, 1, N);
    ans2 = clamp(ans2, 1, N);
    return make_pair(ans1, ans2);
}

Compilation message

communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:52:9: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   52 |     int x = 0;
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2748 KB Output is correct
2 Correct 10 ms 2736 KB Output is correct
3 Correct 9 ms 3568 KB Output is correct
4 Correct 10 ms 2740 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 13 ms 2824 KB Output is correct
7 Correct 20 ms 3020 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 367 ms 2772 KB Output is partially correct
2 Partially correct 209 ms 2760 KB Output is partially correct
3 Partially correct 255 ms 2744 KB Output is partially correct
4 Partially correct 461 ms 2812 KB Output is partially correct
5 Partially correct 355 ms 3216 KB Output is partially correct
6 Partially correct 310 ms 2752 KB Output is partially correct
7 Partially correct 1277 ms 2804 KB Output is partially correct
8 Partially correct 2285 ms 3052 KB Output is partially correct
9 Partially correct 2078 ms 2852 KB Output is partially correct
10 Partially correct 1913 ms 3108 KB Output is partially correct
11 Partially correct 2133 ms 2956 KB Output is partially correct
12 Partially correct 1978 ms 3012 KB Output is partially correct
13 Partially correct 2106 ms 3136 KB Output is partially correct
14 Partially correct 1891 ms 3032 KB Output is partially correct
15 Partially correct 1049 ms 2836 KB Output is partially correct
16 Partially correct 2148 ms 2816 KB Output is partially correct
17 Partially correct 518 ms 2960 KB Output is partially correct
18 Correct 559 ms 2776 KB Output is correct
19 Partially correct 593 ms 3280 KB Output is partially correct
20 Correct 521 ms 3056 KB Output is correct
21 Correct 521 ms 2896 KB Output is correct
22 Partially correct 586 ms 2820 KB Output is partially correct
23 Partially correct 785 ms 2784 KB Output is partially correct
24 Correct 7 ms 2968 KB Output is correct
25 Correct 9 ms 2948 KB Output is correct
26 Correct 11 ms 2756 KB Output is correct
27 Correct 9 ms 2968 KB Output is correct
28 Correct 7 ms 2932 KB Output is correct
29 Correct 22 ms 3020 KB Output is correct
30 Correct 27 ms 3192 KB Output is correct