Submission #987558

#	Time	Username	Problem	Language	Result	Execution time	Memory
987558		cig32	Flight to the Ford (BOI22_communication)	C++17	74 / 100	3166 ms	3484 KiB

communication

#include"communication.h"
#include "bits/stdc++.h"
using namespace std;
//
// --- 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
//
void encode(int N, int X) {

  if(N == 3) {


    vector<int> seq;
    if(X == 1) seq = {0, 0, 0, 0, 0};
    else if(X == 3) seq = {1, 0, 1, 1, 0};
    else seq = {1, 1, 1, 1, 1};
    for(int x: seq) {
      send(x);
    }
    return;
 
  }
  int a[4] = {0, 6, 9, 15};
  vector<pair<int,int>> r;
  r.push_back({1, N});
  int itrs=0;
  while(1) {
    itrs++;
    int ts = 0;
    for(auto x: r) ts += x.second - x.first + 1;
    if(ts <= 2) break;
    vector<pair<int,int>> A[4];
    int cap[4] = {ts/4, ts/4, ts/4, ts - 3 * (ts/4)};
    for(int i=0; i<4; i++) {
      int sum = 0;
      for(int j=0; j<r.size(); j++) {
        sum += r[j].second - r[j].first + 1;
        if(sum >= cap[i]) {
          int diff = sum - cap[i];
          A[i].push_back({r[j].first, r[j].second - diff});
          r[j].first = r[j].second - diff + 1;
          break;
        }
        else if(r[j].first <= r[j].second) {
          A[i].push_back({r[j].first, r[j].second});
          r[j].first = 0;
          r[j].second = -1;
        }

      }
    }
    int actual;
    for(int j=0; j<4; j++) {
      bool yes = 0;
      for(auto x: A[j]) yes |= (x.first <= X && X <= x.second);
      if(yes) actual = j;
    }
    int got = 0;
    for(int i=0; i<4; i++) {
      int s = send((a[actual] & (1 << i)) ? 1 : 0);
      if(s) got |= (1 << i);
    }
    r.clear();
    for(int i=0; i<4; i++) {
      int bruh = a[i] ^ got;
      bool bits[4];
      for(int j=0; j<4; j++) bits[j] = ((bruh & (1 << j)) ? 1 : 0);
      bool bad = 0;
      for(int j=0; j<3; j++) bad |= (bits[j+1] == bits[j] && bits[j] == 1);
      if(bad) continue;
      for(auto x: A[i]) r.push_back(x);
    }
  }
 
}
 
std::pair<int, int> decode(int N) {

  if(N == 3) {

    vector<int> g;
    for(int i=0; i<5; i++) g.push_back(receive());
    int cnt = 0;
    for(int i=0; i<5; i++) cnt += g[i];
    vector<int> h121 = {1, 0, 1, 0, 1};
    vector<int> h122 = {0, 1, 0, 1, 0};
    if(g == h121 || g == h122) return {1, 2};
    else if(cnt < 3) return {1, 3};
    else return {2, 3};
  }
  int a[4] = {0, 6, 9, 15};
  vector<pair<int,int>> r;
  r.push_back({1, N});
  while(1) {
    int ts = 0;
    for(auto x: r) ts += x.second - x.first + 1;
    if(ts <= 2) break;
    vector<pair<int,int>> A[4];
    int cap[4] = {ts/4, ts/4, ts/4, ts - 3 * (ts/4)};
    for(int i=0; i<4; i++) {
      int sum = 0;
      for(int j=0; j<r.size(); j++) {
        sum += r[j].second - r[j].first + 1;
        if(sum >= cap[i]) {
          int diff = sum - cap[i];
          A[i].push_back({r[j].first, r[j].second - diff});
          r[j].first = r[j].second - diff + 1;
          break;
        }
        else if(r[j].first <= r[j].second) {
          A[i].push_back({r[j].first, r[j].second});
          r[j].first = 0;
          r[j].second = -1;
        }

      }
    }
    int got = 0;
    for(int i=0; i<4; i++) {
      int s = receive();
      if(s) got |= (1 << i);
    }
    r.clear();
    for(int i=0; i<4; i++) {
      int bruh = a[i] ^ got;
      bool bits[4];
      for(int j=0; j<4; j++) bits[j] = ((bruh & (1 << j)) ? 1 : 0);
      bool bad = 0;
      for(int j=0; j<3; j++) bad |= (bits[j+1] == bits[j] && bits[j] == 1);
      if(bad) continue;
      for(auto x: A[i]) r.push_back(x);
    }
  }
  vector<int> ss;
  for(auto x: r) {
    for(int i=x.first; i<=x.second; i++) ss.push_back(i);
  }
  if(ss.size() == 2) {
    return {ss[0], ss[1]};
  }
  else {
    return {ss[0], ss[0]};
  }
}
/*
g++ -std=c++17 -O2 -o T2442 sample_grader.cpp T2442.cpp
./T2442 < input.txt
*/

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(int j=0; j<r.size(); j++) {
      |                    ~^~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |       for(int j=0; j<r.size(); j++) {
      |                    ~^~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:68:29: warning: 'actual' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |       int s = send((a[actual] & (1 << i)) ? 1 : 0);
      |                     ~~~~~~~~^

• Subtask 1: 15 / 15
• Subtask 2: 59.00003 / 85