Submission #1236787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236787		Malix	Message (IOI24_message)	C++20	100 / 100	417 ms	868 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

void send_message(std::vector<bool> M, std::vector<bool> C) {
  vector<vector<bool>> a(66,vector<bool>(31,0)),b(66,vector<bool>(31,0));
  vi arr;
  REP(i,0,31)if(C[i]==0)arr.PB(i);
  REP(i,0,16){
    int x=0;
    if(i==15)x=arr[0]+30-arr[i];
    else x=arr[i+1]-arr[i]-1;
    REP(j,0,x)b[j][arr[i]]=1;
    b[x][arr[i]]=1;
    a[x][arr[i]]=1;
  }
  int x=65,y=15;
  for(int i=M.size()-1;i>=0;i--){
    a[x][arr[y]]=M[i];
    b[x][arr[y]]=1;
    while(b[x][arr[y]]){
      y--;
      if(y<0){
        x--;
        y=15;
      }
    }
  }
  a[x][arr[y]]=1;
  REP(i,0,66)send_packet(a[i]);
}

vi c,vis,d;

void dfs(int x){
  vis[x]=1;
  if(c[x]==-1)return;
  d.PB(x);
  if(vis[c[x]]&&d.size()>=16)return;
  if(!vis[c[x]])dfs(c[x]);
  if(d.size()<16)d.pop_back();
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> a) {
  c.clear();d.clear();vis.clear();
  c.resize(31,-1);vis.resize(31,0);
  vector<vector<bool>> b(66,vector<bool>(31,0));
  REP(i,0,31){
    int x=0;
    while(a[x][i]==0){
      b[x][i]=1;
      x++;
      if(x==31)break;
    }
    if(x==31)continue;
    b[x][i]=1;
    c[i]=(i+x+1)%31;
  }
  REP(i,0,31)if(!vis[i]&&d.empty())dfs(i);
  reverse(all(d));
  while(d.size()>16)d.pop_back();
  sort(all(d));
  int x=1,y=0;
  while(b[x][d[y]]||a[x][d[y]]==0){
    y++;
    if(y==16){
      x++;
      y=0;
    }
  }
  b[x][d[y]]=1;
  while(b[x][d[y]]){
    y++;
    if(y==16){
      x++;
      y=0;
    }
  }
  vector<bool> ans;
  while(x<66){
    ans.PB(a[x][d[y]]);
    b[x][d[y]]=1;
    while(x<66&&b[x][d[y]]){
      y++;
      if(y==16){
        x++;
        y=0;
      }
    }
  }
  return ans;
}

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