Submission #1190028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190028		SalihSahin	Message (IOI24_message)	C++20	40.65 / 100	486 ms	856 KiB

message

#include "bits/stdc++.h"
#define pb push_back
#include "message.h"
using namespace std;
#define ll long long

void send_message(vector<bool> M, vector<bool> C){
  int N = M.size();

  vector<bool> A(31, 0), B(31, 1);
  vector<int> cnt(2);
  int f0 = -1, mind = 0;
  for(int i = 0; i < 31; i++){
    vector<bool> pac(31);

    if(f0 != -1){
      pac[f0] = C[i];
      for(int j = 0; j < i; j++){
        if(C[j] == 1 || j == f0 || mind == M.size()) continue;
        pac[j] = M[mind];
        mind++; 
      }

      if(C[i] == 0){
        cnt[0]++;
      }
      else{
        cnt[1]++;
      }
      send_packet(pac);

      if(cnt[0] == 16 || cnt[1] == 15) break;
      continue;
    }

    if(C[i] == 0){
        cnt[0]++;
        if(f0 == -1) f0 = i;
        send_packet(A);
    }
    else{
        cnt[1]++;
        send_packet(B);
    }
    if(cnt[0] == 16 || cnt[1] == 15) break;
  }

    vector<bool> dis_packet = A;
    int bt = 1;
    for(int j = 0; j < 31; j++){
       if(C[j] == 0){
          if(bt > 1024){
            if(mind < N){
              dis_packet[j] = M[mind];
              mind++;
            }
          }
          else{
            if(bt & N) dis_packet[j] = 1;
            bt *= 2;
          }
       }
    }
    send_packet(dis_packet);

  for(int i = mind; i < N; i += 16){
    vector<bool> packet = A;
    int ind = 0;
    for(int j = 0; j < 31; j++){
        if(C[j] == 1) continue;
        if(i + ind < N) packet[j] = M[i + ind];
        ind++;
    }
    send_packet(packet);
  }
}

vector<bool> receive_message(vector<vector<bool>> R){
    int n = R.size();
    int ind = 0;

    vector<bool> message;
    vector<int> C(31);
    vector<int> cnt(2);
    int f0 = -1;
    for(int i = 0; i < 31; i++){
        int sum = 0;
        for(auto itr: R[i]){
            sum += itr;
        }

        if(f0 != -1){
           for(int j = 0; j < i; j++){
            if(C[j] == 1 || j == f0) continue;
            message.pb(R[i][j]);
           }
           if(R[i][f0] == 0){
              C[i] = 0;
              cnt[0]++;
           }
           else{
             C[i] = 1;
             cnt[1]++;
           }
        }
        else{
          if(sum >= 16){
              C[i] = 1;
              cnt[1]++;
          }
          else{
              C[i] = 0;
              if(f0 == -1) f0 = i;
              cnt[0]++;
          }
        }

        ind++;
        if(cnt[0] == 16 || cnt[1] == 15) break;
    }
    if(cnt[0] == 16){
        for(int i = ind; i < 31; i++){
            C[i] = 1;
        }
    }
    else{
        for(int i = ind; i < 31; i++){
            C[i] = 0;
        }
    }

    /*
    cout<<"C arrayi : "<<endl;
    for(int i = 0; i < 31; i++){
        cout<<C[i]<<" ";
    }
    cout<<endl;
    */

    int len = 0, bt = 1;
    for(int i = ind; i <= ind; i++){
        for(int j = 0; j < 31; j++){
            if(C[j] == 0){
                if(bt > 1024 && message.size() < len){
                  message.pb(R[i][j]);
                }
                else{
                  if(R[i][j] == 1) len += bt;
                  bt *= 2;
                }
            }
        }
    }
    ind++;

    for(int i = ind; i < n; i++){
        for(int j = 0; j < 31; j++){
            if(C[j] == 0) message.pb(R[i][j]);
        }
    }
    while(message.size() > len) message.pop_back();

    return message;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 30.6505 / 90