oj.uz

Submission #601734

# Submission time Handle Problem Language Result Execution time Memory
601734 2022-07-22T09:28:17 Z 박상훈(#8471) Flight to the Ford (BOI22_communication) C++17
77 / 100
 4516 ms 2332 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<1024;i++){
        valid[i] = 1;
        for (int j=0;j<9;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, 1024, X, 10);
    //process(V, S, 512, X, 9);
    process(V, S, 256, X, 8);
    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<1024;i++){
        valid[i] = 1;
        for (int j=0;j<9;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, 1024, 0, 10);
    //process(V, S, 512, 0, 9);
    process(V, S, 256, 0, 8);
    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]};
}

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:131:18: warning: iteration 128 invokes undefined behavior [-Waggressive-loop-optimizations]
  131 |         valid[i] = 1;
      |         ~~~~~~~~~^~~
communication.cpp:130:19: note: within this loop
  130 |     for (int i=0;i<1024;i++){
      |                  ~^~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:168:18: warning: iteration 128 invokes undefined behavior [-Waggressive-loop-optimizations]
  168 |         valid[i] = 1;
      |         ~~~~~~~~~^~~
communication.cpp:167:19: note: within this loop
  167 |     for (int i=0;i<1024;i++){
      |                  ~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1800 KB Output is correct
2 Correct 18 ms 1744 KB Output is correct
3 Correct 25 ms 1684 KB Output is correct
4 Correct 13 ms 1752 KB Output is correct
5 Correct 19 ms 1700 KB Output is correct
6 Correct 35 ms 1968 KB Output is correct
7 Correct 53 ms 2104 KB Output is correct

Subtask #2
62.00002 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 780 ms 1880 KB Output is partially correct
2 Partially correct 465 ms 1784 KB Output is partially correct
3 Partially correct 674 ms 1916 KB Output is partially correct
4 Partially correct 988 ms 1784 KB Output is partially correct
5 Partially correct 647 ms 1856 KB Output is partially correct
6 Partially correct 774 ms 1856 KB Output is partially correct
7 Partially correct 3185 ms 2088 KB Output is partially correct
8 Partially correct 4516 ms 2332 KB Output is partially correct
9 Partially correct 3989 ms 2104 KB Output is partially correct
10 Partially correct 4217 ms 2084 KB Output is partially correct
11 Partially correct 4092 ms 2076 KB Output is partially correct
12 Partially correct 3763 ms 2124 KB Output is partially correct
13 Partially correct 3818 ms 2016 KB Output is partially correct
14 Partially correct 3788 ms 2160 KB Output is partially correct
15 Partially correct 1988 ms 2008 KB Output is partially correct
16 Partially correct 4462 ms 1992 KB Output is partially correct
17 Partially correct 994 ms 1796 KB Output is partially correct
18 Partially correct 939 ms 1988 KB Output is partially correct
19 Partially correct 1064 ms 1920 KB Output is partially correct
20 Partially correct 1186 ms 1968 KB Output is partially correct
21 Partially correct 880 ms 2064 KB Output is partially correct
22 Partially correct 1064 ms 1948 KB Output is partially correct
23 Partially correct 1624 ms 1896 KB Output is partially correct
24 Correct 10 ms 1808 KB Output is correct
25 Correct 12 ms 1820 KB Output is correct
26 Correct 20 ms 1740 KB Output is correct
27 Correct 14 ms 1720 KB Output is correct
28 Correct 18 ms 1824 KB Output is correct
29 Correct 35 ms 1664 KB Output is correct
30 Correct 35 ms 1800 KB Output is correct