제출 #1242416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242416		noyancanturk	Message (IOI24_message)	C++20	76.16 / 100	956 ms	876 KiB

message

#include "message.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

void send_message(vector<bool>m,vector<bool>c){
  // cerr<<"enter1\n";
  srand(1);
  int maybe=31;
  int bad[31]{},trust[31]{},accuse[31]{},haveinfo[31]{};
  for(int i=0;i<31;i++){
    trust[i]=1<<i;
  }
  #define has(mask,i) ((mask>>i)&1)
  while(16<maybe){
    vector<bool>tosend(31,0);
    int edges[31];
    int did=0;
    for(int i=0;i<31;i++){
      edges[i]=-1;
      if(bad[i])continue;
      vector<int>noinfo;
      for(int j=0;j<31;j++){
        if(bad[j])continue;
        int nope=0;
        for(int k=0;k<31;k++){
          if(has(trust[i],k)&&has(haveinfo[k],j)){
            nope=1;
            break;
          }
        }
        if(!nope){
          noinfo.pb(j);
        }
      }
      if(noinfo.size()){
        edges[i]=noinfo[rand()%noinfo.size()];
        haveinfo[i]|=1<<edges[i];
        did++;
      }
    }
    // cerr<<did<<'\n';
    // for(int i=0;i<31;i++){
    //   cerr<<c[i]<<' '<<bad[i]<<' '<<__builtin_popcount(trust[i])<<' ';
    //   for(int j=0;j<31;j++){
    //     cerr<<has(trust[i],j);
    //   }cerr<<'\n';
    // }cerr<<'\n';
    // for(int i=0;i<31;i++){
    //   for(int j=0;j<31;j++){
    //     if(!c[i]&&c[j]&&has(trust[i],j)){
    //       cerr<<"what "<<i<<' '<<j<<'\n';
    //       assert(0);
    //     }
    //   }
    // }
    // assert(did);
    for(int i=0;i<31;i++){
      if(edges[i]!=-1)tosend[i]=!c[edges[i]];
    }
    vector<bool>sent=send_packet(tosend);
    for(int i=0;i<31;i++){
      if(edges[i]!=-1){
        if(sent[i]==1){
          trust[i]|=1<<edges[i];
        }else{
          accuse[i]|=1<<edges[i];
        }
      }
    }
    int change=1;
    while(change){
      change=0;
      for(int i=0;i<31;i++){
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&((trust[i]|trust[j])!=trust[i]||(accuse[i]|accuse[j])!=accuse[i])){
            trust[i]|=trust[j];
            accuse[i]|=accuse[j];
            change=1;
          }
        }
      }
    }
    int havetrust[31]{},haveaccuse[31]{};
    for(int i=0;i<31;i++){
      for(int j=0;j<31;j++){
        if(has(trust[i],j)){
          havetrust[j]++;
        }
        if(has(accuse[i],j)){
          haveaccuse[j]++;
        }
      }
    }
    for(int i=0;i<31;i++){
      if(bad[i])continue;
      if(15<haveaccuse[i]){
        bad[i]=1;
        maybe--;
      }
      if(15<havetrust[i]){
        for(int j=0;j<31;j++){
          if(bad[j])continue;
          if(has(accuse[i],j)){
            bad[j]=1;
            maybe--;
          }
        }
      }
    }
    for(int i=0;i<31;i++){
      if(16<__builtin_popcount(trust[i])||15<__builtin_popcount(accuse[i])||(trust[i]&accuse[i])||has(accuse[i],i)){
        bad[i]=1;
      }
    }
    change=1;
    while(change){
      for(int i=0;i<31;i++){
        change=0;
        if(bad[i])continue;
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&bad[j]){
            bad[i]=1;
            maybe--;
            change=1;
            break;
          }
        }
      }
    }
    for(int i=0;i<31;i++){
      haveinfo[i]=trust[i]|accuse[i];
    }
    for(int i=0;i<31;i++){
      if(!bad[i]&&__builtin_popcount(trust[i])==16){
        int ok=0;
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&has(trust[j],i)){
            ok++;
          }
        }
        if(ok==16){
          for(int j=0;j<31;j++){
            bad[j]=!has(trust[i],j);
          }
          maybe=16;
          break;
        }
      }
    }
  }
  vector<int>good;
  for(int i=0;i<31;i++){
    assert(bad[i]==c[i]);
    if(!bad[i]){
      good.pb(i);
    }
  }
  int n=m.size();
  vector<bool>tosend(31,0);
  for(int i=0;i<16;i++){
    tosend[good[i]]=has(n,i);
  }
  send_packet(tosend);
  for(int i=0;i<n;){
    for(int j=0;j<16;j++,i++){
      if(n<=i)tosend[good[j]]=0;
      else tosend[good[j]]=m[i];
    }
    send_packet(tosend);
  }
}

vector<bool>receive_message(vector<vector<bool>>ms){
  srand(1);
  int maybe=31;
  int bad[31]{},trust[31]{},accuse[31]{},haveinfo[31]{};
  for(int i=0;i<31;i++){
    trust[i]=1<<i;
  }
  int nxt=0;
  #define has(mask,i) ((mask>>i)&1)
  while(16<maybe){
    vector<bool>tosend(31,0);
    int edges[31];
    for(int i=0;i<31;i++){
      edges[i]=-1;
      if(bad[i])continue;
      vector<int>noinfo;
      for(int j=0;j<31;j++){
        if(bad[j])continue;
        int nope=0;
        for(int k=0;k<31;k++){
          if(has(trust[i],k)&&has(haveinfo[k],j)){
            nope=1;
            break;
          }
        }
        if(!nope){
          noinfo.pb(j);
        }
      }
      if(noinfo.size()){
        edges[i]=noinfo[rand()%noinfo.size()];
        haveinfo[i]|=1<<edges[i];
      }
    }
    vector<bool>sent=ms[nxt++];
    for(int i=0;i<31;i++){
      if(edges[i]!=-1){
        if(sent[i]==1){
          trust[i]|=1<<edges[i];
        }else{
          accuse[i]|=1<<edges[i];
        }
      }
    }
    int change=1;
    while(change){
      change=0;
      for(int i=0;i<31;i++){
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&((trust[i]|trust[j])!=trust[i]||(accuse[i]|accuse[j])!=accuse[i])){
            trust[i]|=trust[j];
            accuse[i]|=accuse[j];
            change=1;
          }
        }
      }
    }
    int havetrust[31]{},haveaccuse[31]{};
    for(int i=0;i<31;i++){
      for(int j=0;j<31;j++){
        if(has(trust[i],j)){
          havetrust[j]++;
        }
        if(has(accuse[i],j)){
          haveaccuse[j]++;
        }
      }
    }
    for(int i=0;i<31;i++){
      if(bad[i])continue;
      if(15<haveaccuse[i]){
        bad[i]=1;
        maybe--;
      }
      if(15<havetrust[i]){
        for(int j=0;j<31;j++){
          if(bad[j])continue;
          if(has(accuse[i],j)){
            bad[j]=1;
            maybe--;
          }
        }
      }
    }
    for(int i=0;i<31;i++){
      if(16<__builtin_popcount(trust[i])||15<__builtin_popcount(accuse[i])||(trust[i]&accuse[i])||has(accuse[i],i)){
        bad[i]=1;
      }
    }
    change=1;
    while(change){
      for(int i=0;i<31;i++){
        change=0;
        if(bad[i])continue;
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&bad[j]){
            bad[i]=1;
            maybe--;
            change=1;
            break;
          }
        }
      }
    }
    for(int i=0;i<31;i++){
      haveinfo[i]=trust[i]|accuse[i];
    }
    for(int i=0;i<31;i++){
      if(!bad[i]&&__builtin_popcount(trust[i])==16){
        int ok=0;
        for(int j=0;j<31;j++){
          if(has(trust[i],j)&&has(trust[j],i)){
            ok++;
          }
        }
        if(ok==16){
          for(int j=0;j<31;j++){
            bad[j]=!has(trust[i],j);
          }
          maybe=16;
          break;
        }
      }
    }
  }
  vector<int>good;
  for(int i=0;i<31;i++){
    if(!bad[i]){
      good.pb(i);
    }
  }
  int n=0;
  vector<bool>tosend=ms[nxt++];
  for(int i=0;i<16;i++){
    n|=int(tosend[good[i]])<<i;
  }
  vector<bool>m(n);
  for(int i=0;i<n;){
    assert(nxt<ms.size());
    tosend=ms[nxt++];
    for(int j=0;j<16;j++,i++){
      if(n<=i)break;
      else m[i]=tosend[good[j]];
    }
  }
  return m;
}

// void send_message(std::vector<bool> M, std::vector<bool> C) {
//   std::vector<bool> A(31, 0);
//   send_packet(A);
// }

// std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
//   return std::vector<bool>({0, 1, 1, 0});
// }

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