Submission #1130586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130586		naneosmic	Message (IOI24_message)	C++20	100 / 100	590 ms	892 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
void send_message(vector<bool> M, vector<bool> C) {
    vector<vector<ll>>message(66,vector<ll>(31));
    ll n=M.size();
    bool last=M[n-1];
    if(last)last=false;
    else last=true;
    while(n<1025LL){
        M.push_back(last);
        n++;
    }
    n=M.size();
    for(ll i=0;i<31;i++){
        if(C[i]==0){
            for(ll j=0;j<66;j++){
                message[j][i]=-1;
            }
        }else{
            for(ll j=0;j<66;j++){
                message[j][i]=0;
            }
        }
    }
    vector<ll>idx;
    for(int i=0;i<31;i++)if(C[i]==0)idx.push_back(i);
    idx.push_back(idx[0]);
    vector<int>second(31);
    for(int i=0;i<16;i++){
        second[i]=(31+idx[i+1]-idx[i])%31;
    }
    for(int i=0;i<16;i++){
        for(int j=0;j<second[i]-1;j++){
            message[j][idx[i]]=0;
        }
        message[second[i]-1][idx[i]]=1;
    }
    int pointer=0;
    for(int i=0;i<66;i++){
        for(int j=0;j<31;j++){
            if(message[i][j]==-1){
                message[i][j]=M[pointer];
                pointer++;
            }
        }
    }
    for(ll i=0;i<66;i++){
        vector<bool>r(31);
        for(int j=0;j<31;j++){
            if(message[i][j]==0){
                r[j]=false; 
            }else {
                r[j]=true;
            }
        }
        send_packet(r);
    }
}
vector<bool> receive_message(vector<vector<bool>> R) {
    vector<vector<ll>>message(66,vector<ll>(31));
    for(int i=0;i<66;i++){
        for(int j=0;j<31;j++){
            if(R[i][j])message[i][j]=1;
            else message[i][j]=0;
        }
    }
    vector<int>diff(31);
    for(int i=0;i<31;i++){
        int num=0;
        for(int j=0;j<31;j++){
            if(R[j][i]==1){
                num=j+1;
                break;
            }
        }
        diff[i]=num;
    }
    vector<int>next(31);
    for(int i=0;i<31;i++){
        next[i]=(i+diff[i])%31;
    }
    vector<bool>r={};
    vector<int>idx;
    vector<int>bad;
    for(int i=0;i<31;i++){
        int curr=i;
        bool flag=true;
        for(int j=0;j<15;j++){
            curr=next[curr];
            if(curr==i){
                flag=false;
                break;
            }
        }
        curr=next[curr];
        if(curr!=i)flag=false;
        if(flag)idx.push_back(i);
        else bad.push_back(i);
    }
    for(int i=0;i<15;i++){
        for(int j=0;j<66;j++){
            message[j][bad[i]]=-1;
        }
    }
    for(int i=0;i<16;i++){
        for(int j=0;j<66;j++){
            if(message[j][idx[i]]==1){
                message[j][idx[i]]=-1;
                break;
            }else{
                message[j][idx[i]]=-1;
            }
        }
    }
    for(int i=0;i<66;i++){
        for(int j=0;j<31;j++){
            if(message[i][j]!=-1){
                bool val;
                if(message[i][j]==1)val=true;
                else val=false;
                r.push_back(val);
            }
        }
    }
    bool last=r[1024];
    int sz=r.size()-1;
    while(r[sz]==last){
        sz--;
        r.pop_back();
    }
    return r;
}

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