oj.uz

답안 #601728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601728 2022-07-22T09:26:21 Z 박상훈(#8471) Flight to the Ford (BOI22_communication) C++17
77 / 100
 4263 ms 2124 KB 
#include "communication.h"
#include <bits/stdc++.h>
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//

using namespace std;
typedef long long ll;
int valid[128];

int _find(const vector<pair<int, int>> &V, int S, int k, int X){
    int cur = V[0].first;
    int pt = 0;
    int ret = 0;

    int rem = S / k;
    if (S%k) rem++;

    while(true){
        int r = min(cur+rem-1, V[pt].second);
        if (X>=cur && X<=r) return ret;

        S -= r-cur+1;
        rem -= r-cur+1;
        if (rem==0){
            --k;
            assert(k);

            rem = S/k;
            if (S%k) rem++;
            ret++;
        }

        cur = r+1;
        if (cur>V[pt].second){
            ++pt;
            cur = V[pt].first;
        }
    }
    assert(0);
}

void _modify(vector<pair<int, int>> &V, int &S, int k, int val){
    vector<pair<int, int>> ret;
    int retS = 0;

    int cur = V[0].first;
    int pt = 0, idx = 0;

    int rem = S / k;
    if (S%k) rem++;

    while(true){
        int r = min(cur+rem-1, V[pt].second);
        if (valid[idx^val]){
            //printf(" %d %d\n", idx, val);
            ret.emplace_back(cur, r);
            retS += r-cur+1;
        }

        S -= r-cur+1;
        rem -= r-cur+1;
        if (rem==0){
            --k;
            if (!k) break;

            rem = S/k;
            if (S%k) rem++;
            idx++;
        }

        cur = r+1;
        if (cur>V[pt].second){
            ++pt;
            cur = V[pt].first;
        }
    }

    swap(V, ret);
    swap(S, retS);
}

vector<int> get_last(const vector<pair<int, int>> &V){
    vector<int> ret;
    for (auto &[l, r]:V){
        for (int i=l;i<=r;i++) ret.push_back(i);
    }
    assert(ret.size()==3);
    return ret;
}

void process(vector<pair<int, int>> &V, int &S, int k, int encode, int t){
    while(S>=k){
        int val = 0;
        if (encode) val = _find(V, S, k, encode);
        int rval = 0;

        if (encode){
            for (int i=0;i<t;i++){
                if (val&(1<<i)) rval |= (send(1)<<i);
                else rval |= (send(0)<<i);
            }
        }

        else{
            for (int i=0;i<t;i++){
                rval |= (receive()<<i);
            }
        }


        _modify(V, S, k, rval);

        //for (auto &[l, r]:V) printf("[%d, %d] ", l, r);
        //printf("-> %d\n", S);
    }
}

void encode(int N, int X) {

    for (int i=0;i<128;i++){
        valid[i] = 1;
        for (int j=0;j<6;j++) if ((i&(1<<j)) && (i&(1<<(j+1)))) valid[i] = 0;
    }

    vector<pair<int, int>> V = {{1, N}};
    int S = N;

    process(V, S, 128, X, 7);
    process(V, S, 64, X, 6);
    process(V, S, 32, X, 5);
    process(V, S, 16, X, 4);
    process(V, S, 8, X, 3);
    process(V, S, 4, X, 2);




    vector<int> last = get_last(V);
    X = find(last.begin(), last.end(), X) - last.begin() + 1;
    assert(X<=3);
    string s[4] = {"", "10", "11", "01"};

    bool flag = 0;
    for (int i=0;i<3;i++){
        if (!flag) flag = (((s[X][0]-'0')^1) != send((s[X][0]-'0') ^ 1));
        else{
            send(s[X][1]-'0');
            flag = 0;
        }
    }
}

std::pair<int, int> decode(int N) {
    for (int i=0;i<128;i++){
        valid[i] = 1;
        for (int j=0;j<6;j++) if ((i&(1<<j)) && (i&(1<<(j+1)))) valid[i] = 0;
    }

    vector<pair<int, int>> V = {{1, N}};
    int S = N;

    process(V, S, 128, 0, 7);
    process(V, S, 64, 0, 6);
    process(V, S, 32, 0, 5);
    process(V, S, 16, 0, 4);
    process(V, S, 8, 0, 3);
    process(V, S, 4, 0, 2);

    vector<int> last = get_last(V);
    vector<int> v;
    for (int i=0;i<3;i++){
        int x = receive();
        v.push_back(x);
        if (i && v[i-1]==v[i]){
            if (v[i]==1) return {last[1], last[2]};
            else return {last[0], last[1]};
        }
    }
    return {last[0], last[2]};
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1760 KB Output is correct
2 Correct 13 ms 1808 KB Output is correct
3 Correct 16 ms 1800 KB Output is correct
4 Correct 9 ms 1836 KB Output is correct
5 Correct 12 ms 1640 KB Output is correct
6 Correct 26 ms 1988 KB Output is correct
7 Correct 44 ms 1800 KB Output is correct

Subtask #2
62.00002 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 844 ms 1748 KB Output is partially correct
2 Partially correct 313 ms 1892 KB Output is partially correct
3 Partially correct 596 ms 1788 KB Output is partially correct
4 Partially correct 1005 ms 1776 KB Output is partially correct
5 Partially correct 951 ms 1936 KB Output is partially correct
6 Partially correct 549 ms 1840 KB Output is partially correct
7 Partially correct 2849 ms 1996 KB Output is partially correct
8 Partially correct 4263 ms 2124 KB Output is partially correct
9 Partially correct 3864 ms 1888 KB Output is partially correct
10 Partially correct 3828 ms 1960 KB Output is partially correct
11 Partially correct 3487 ms 1960 KB Output is partially correct
12 Partially correct 3421 ms 1796 KB Output is partially correct
13 Partially correct 3671 ms 1976 KB Output is partially correct
14 Partially correct 3513 ms 1928 KB Output is partially correct
15 Partially correct 1940 ms 1804 KB Output is partially correct
16 Partially correct 4133 ms 1892 KB Output is partially correct
17 Partially correct 887 ms 1884 KB Output is partially correct
18 Partially correct 1051 ms 1984 KB Output is partially correct
19 Partially correct 1071 ms 1828 KB Output is partially correct
20 Partially correct 1013 ms 1816 KB Output is partially correct
21 Partially correct 1102 ms 1940 KB Output is partially correct
22 Partially correct 1130 ms 1896 KB Output is partially correct
23 Partially correct 1727 ms 2064 KB Output is partially correct
24 Correct 12 ms 1796 KB Output is correct
25 Correct 15 ms 2020 KB Output is correct
26 Correct 17 ms 1880 KB Output is correct
27 Correct 11 ms 1672 KB Output is correct
28 Correct 17 ms 1804 KB Output is correct
29 Correct 32 ms 1920 KB Output is correct
30 Correct 39 ms 1896 KB Output is correct