Submission #908659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
908659	2024-01-16T15:59:38 Z	GrandTiger1729	Flight to the Ford (BOI22_communication)	C++17	90 / 100	2125 ms	3184 KB

communication

#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);
    int re[4]{};
    bool f = 0;
    for (int y = 1; y <= 29; y++)
    {
        if (1 << y > N)
        {
            break;
        }
        if (!f)
        {
            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;
            f = 0;
            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;
            f = 0;
        }
        else
        {
            res[re[0] ^ re[1] ^ 1].push_back(y);
            re[0] = re[3];
            f = 1;
        }
    }
}

pair<int, int> decode(int N)
{
    int ans = 0;
    vector<int> res[2];
    int x = 0;
    res[0].push_back(0);
    int re[4]{};
    bool f = 0;
    for (int y = 1; y <= 29; y++)
    {
        if (1 << y > N)
        {
            break;
        }
        if (!f)
        {
            re[0] = receive();
        }
        re[1] = receive();
        re[2] = receive();
        if (re[1] == re[2])
        {
            ans ^= re[1] << y;
            f = 0;
            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;
            f = 0;
        }
        else
        {
            res[re[0] ^ re[1] ^ 1].push_back(y);
            re[0] = re[3];
            f = 1;
        }
    }
    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:60:9: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   60 |     int x = 0;
      |         ^

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2928 KB	Output is correct
2	Correct	9 ms	2932 KB	Output is correct
3	Correct	12 ms	2760 KB	Output is correct
4	Correct	11 ms	2740 KB	Output is correct
5	Correct	11 ms	2936 KB	Output is correct
6	Correct	15 ms	3184 KB	Output is correct
7	Correct	20 ms	2864 KB	Output is correct

Subtask #2

75.000005 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	369 ms	2728 KB	Output is partially correct
2	Partially correct	149 ms	2760 KB	Output is partially correct
3	Partially correct	222 ms	2760 KB	Output is partially correct
4	Partially correct	442 ms	3020 KB	Output is partially correct
5	Partially correct	358 ms	2736 KB	Output is partially correct
6	Correct	312 ms	2716 KB	Output is correct
7	Correct	1351 ms	2860 KB	Output is correct
8	Correct	2125 ms	3004 KB	Output is correct
9	Correct	1734 ms	3112 KB	Output is correct
10	Correct	1800 ms	2892 KB	Output is correct
11	Correct	1943 ms	3024 KB	Output is correct
12	Correct	1758 ms	2976 KB	Output is correct
13	Correct	1807 ms	2884 KB	Output is correct
14	Correct	1942 ms	3028 KB	Output is correct
15	Correct	983 ms	2824 KB	Output is correct
16	Correct	2059 ms	2832 KB	Output is correct
17	Correct	476 ms	2828 KB	Output is correct
18	Correct	495 ms	2812 KB	Output is correct
19	Correct	504 ms	2884 KB	Output is correct
20	Correct	519 ms	2960 KB	Output is correct
21	Correct	484 ms	2876 KB	Output is correct
22	Correct	454 ms	2824 KB	Output is correct
23	Correct	693 ms	2840 KB	Output is correct
24	Correct	4 ms	2716 KB	Output is correct
25	Correct	9 ms	2708 KB	Output is correct
26	Correct	9 ms	2780 KB	Output is correct
27	Correct	10 ms	2776 KB	Output is correct
28	Correct	5 ms	3132 KB	Output is correct
29	Correct	16 ms	2804 KB	Output is correct
30	Correct	23 ms	2744 KB	Output is correct