oj.uz

Submission #601699

# Submission time Handle Problem Language Result Execution time Memory
601699 2022-07-22T09:16:19 Z 박상훈(#8471) Flight to the Ford (BOI22_communication) C++17
15 / 100
 50 ms 1948 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[64];

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){
    while(S>=k){
        int val = 0;
        if (encode) val = _find(V, S, k, encode);
        int rval = 0;

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

        else{
            for (int i=0;i<2;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<64;i++){
        valid[i] = 1;
        for (int j=0;j<5;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, 8, X);
    process(V, S, 4, X);




    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<64;i++){
        valid[i] = 1;
        for (int j=0;j<5;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, 8, 0);
    process(V, S, 4, 0);

    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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1776 KB Output is correct
2 Correct 13 ms 1884 KB Output is correct
3 Correct 17 ms 1768 KB Output is correct
4 Correct 9 ms 1740 KB Output is correct
5 Correct 11 ms 1948 KB Output is correct
6 Correct 30 ms 1720 KB Output is correct
7 Correct 50 ms 1700 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -