oj.uz

Submission #823996

# Submission time Handle Problem Language Result Execution time Memory
823996 2023-08-13T11:14:50 Z ttamx Flight to the Ford (BOI22_communication) C++17
74 / 100
 2726 ms 2164 KB 
#include"communication.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

void encode(int N, int X){
    vector<int> val={0,6,9,15};
    vector<int> bit;
    vector<vector<int>> vec(16);
    for(int i=0;i<16;i++){
        bool ok=true;
        for(int j=0;j<3;j++)ok&=(i>>j&3)!=3;
        if(ok)bit.emplace_back(i);
    }
    for(int i=0;i<4;i++)for(auto x:bit)vec[val[i]^x].emplace_back(i);
    auto give=[&](int x){
        int num=0;
        for(int i=0;i<4;i++)num|=send(val[x]>>i&1)<<i;
        return vec[num];
    };
    function<void(vector<p2>)> sol=[&](vector<p2> itv){
        int sz=0;
        for(auto [l,r]:itv)sz+=r-l+1;
        if(sz<=2)return;
        sz=(sz+3)/4;
        int cnt=0,cur=0;
        vector<vector<p2>> block(4);
        for(auto [l,r]:itv){
            block[cur].emplace_back(l,r);
            cnt+=r-l+1;
            while(cnt>=sz){
                int dif=cnt-sz;
                block[cur].back().second-=dif;
                cur++;
                if(dif>0)block[cur].emplace_back(r-dif+1,r);
                cnt=dif;
            }
        }
        int id=0;
        for(int i=0;i<4;i++)for(auto [l,r]:block[i])if(l<=X&&X<=r)id=i;
        auto tmp=give(id);
        vector<p2> res=block[tmp[0]];
        for(auto x:block[tmp[1]])res.emplace_back(x);
        sol(res);
    };
    sol({{1,N}});
}

pair<int, int> decode(int N) {
    vector<int> val={0,6,9,15};
    vector<int> bit;
    vector<vector<int>> vec(16);
    for(int i=0;i<16;i++){
        bool ok=true;
        for(int j=0;j<3;j++)ok&=(i>>j&3)!=3;
        if(ok)bit.emplace_back(i);
    }
    for(int i=0;i<4;i++)for(auto x:bit)vec[val[i]^x].emplace_back(i);
    auto get=[&](){
        int num=0;
        for(int i=0;i<4;i++)num|=receive()<<i;
        return vec[num];
    };
    vector<int> ans;
    function<void(vector<p2>)> sol=[&](vector<p2> itv){
        int sz=0;
        for(auto [l,r]:itv)sz+=r-l+1;
        if(sz<=2){
            for(auto [l,r]:itv)for(int i=l;i<=r;i++)ans.emplace_back(i);
            while(ans.size()<2)ans.emplace_back(1);
            return;
        }
        sz=(sz+3)/4;
        int cnt=0,cur=0;
        vector<vector<p2>> block(4);
        for(auto [l,r]:itv){
            block[cur].emplace_back(l,r);
            cnt+=r-l+1;
            while(cnt>=sz){
                int dif=cnt-sz;
                block[cur].back().second-=dif;
                cur++;
                if(dif>0)block[cur].emplace_back(r-dif+1,r);
                cnt=dif;
            }
        }
        auto tmp=get();
        vector<p2> res=block[tmp[0]];
        for(auto x:block[tmp[1]])res.emplace_back(x);
        sol(res);
    };
    sol({{1,N}});
    return {ans[0],ans[1]};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1712 KB Output is correct
2 Correct 7 ms 1752 KB Output is correct
3 Correct 9 ms 1740 KB Output is correct
4 Correct 8 ms 1688 KB Output is correct
5 Correct 9 ms 1684 KB Output is correct
6 Correct 21 ms 1752 KB Output is correct
7 Correct 34 ms 1684 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 570 ms 1768 KB Output is partially correct
2 Partially correct 283 ms 1792 KB Output is partially correct
3 Partially correct 433 ms 1880 KB Output is partially correct
4 Partially correct 760 ms 1820 KB Output is partially correct
5 Partially correct 592 ms 1772 KB Output is partially correct
6 Partially correct 434 ms 1864 KB Output is partially correct
7 Partially correct 1634 ms 1928 KB Output is partially correct
8 Partially correct 2673 ms 2164 KB Output is partially correct
9 Partially correct 2597 ms 2116 KB Output is partially correct
10 Partially correct 2684 ms 2000 KB Output is partially correct
11 Partially correct 2462 ms 1888 KB Output is partially correct
12 Partially correct 2548 ms 2148 KB Output is partially correct
13 Partially correct 2309 ms 1928 KB Output is partially correct
14 Partially correct 2156 ms 2108 KB Output is partially correct
15 Partially correct 1259 ms 2032 KB Output is partially correct
16 Partially correct 2726 ms 1916 KB Output is partially correct
17 Partially correct 716 ms 1940 KB Output is partially correct
18 Partially correct 755 ms 1836 KB Output is partially correct
19 Partially correct 708 ms 1952 KB Output is partially correct
20 Partially correct 719 ms 2036 KB Output is partially correct
21 Partially correct 697 ms 1992 KB Output is partially correct
22 Partially correct 621 ms 1940 KB Output is partially correct
23 Partially correct 1091 ms 1832 KB Output is partially correct
24 Correct 8 ms 1724 KB Output is correct
25 Correct 7 ms 1704 KB Output is correct
26 Correct 9 ms 1716 KB Output is correct
27 Correct 6 ms 1684 KB Output is correct
28 Correct 9 ms 1756 KB Output is correct
29 Correct 21 ms 1772 KB Output is correct
30 Correct 28 ms 1712 KB Output is correct