Submission #1130535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130535		ThylOne	Message (IOI24_message)	C++20	100 / 100	585 ms	856 KiB

message

#include "message.h"
#include <algorithm>
#include<bits/stdc++.h>

using namespace std;
void send_message(std::vector<bool> M, std::vector<bool> C) {
    vector<int> pos_mine;
    for (int i = 0; i < 31; i++)
      if (!C[i])
        pos_mine.push_back(i);

    //On ajoute le hot one flag
    reverse(M.begin(),M.end()); // On reverse l'ordre du message
    M.push_back(1);
    while(M.size()!=1025)M.push_back(0);
    reverse(M.begin(),M.end());
  
    //On ajoute le hot one flag
    //On crée les futurs packets
    vector<vector<bool>> packets(66);
    vector<vector<bool>> writen(66);
    for(int i = 0;i<66;i++)packets[i].resize(31,false);
    for(int i = 0;i<66;i++)writen[i] .resize(31,false);

    //On encode le graphe fonctionnel
    for(int i = 0;i<16;i++){
        int nxt_pos = (pos_mine[(i+1)%16]-pos_mine[i])%31;
        if(nxt_pos<0)nxt_pos = 31+nxt_pos;
        for(int j=0;j<nxt_pos-1;j++){
            packets[j][pos_mine[i]] =  0;
            writen[j][pos_mine[i]] = 1;
        }
        packets[nxt_pos-1][pos_mine[i]] = 1;
        writen[nxt_pos-1][pos_mine[i]] = 1;
    }

    //On écrit le message aux endroits restants
    int act_bit = 0;
    for(int p =0;p<66;p++){
        for(int m:pos_mine){
          if(!writen[p][m]){
            packets[p][m] = M[act_bit++];
          }
        }
    }
   
    for(int i = 0;i<66;i++){
      send_packet(packets[i]);
    }
   
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vector<bool> re;

  int nxt[31];
  bool readable[66][31];
  for(int p = 0;p<66;p++)
    fill(readable[p],readable[p]+31,true);

  for(int i = 0;i<31;i++){
    for(int p = 0;p<31;p++){
      readable[p][i] = false;
      if(R[p][i]){
        nxt[i] = p+1;break;
      }
    }
  }
  vector<int> mine;
  for(int i = 0;i<31;i++){
    vector<int> composante;
    vector<bool> mem(31,false);
    int act = i;
    while(mem[act] == false){
      composante.push_back(act);
      mem[act] = true;
      act = (act + nxt[act])%31;
    }
    if(composante.size()==16){
      mine = composante;break;
    }
  }


  //Maintenant on a que à lire le msg
  bool OK = false;
  int cnt = 0;
  for(int p = 0;p<66;p++){
    for(int i :mine){
      if(!readable[p][i])continue;
      if(OK)re.push_back(R[p][i]);
      if(!OK)cnt++;
      if(R[p][i]==1)OK=true;
    }
  }
  return re;
}

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