Submission #1275481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275481		mkkkkkkkk	Message (IOI24_message)	C++20	100 / 100	402 ms	856 KiB

message

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

using namespace std;


void send_message(std::vector<bool> M, std::vector<bool> C)
{
    vector<vector<int>> R;
    vector<int> temp;
    for(int i=0;i<31;i++)
    {
        temp.push_back(-1);
    }
    for(int i=0;i<66;i++)
    {
        R.push_back(temp);
    }
    temp.clear();
    for(int br=1025-M.size();br>1;br--)
    {
        temp.push_back(0);
    }
    temp.push_back(1);
    for(auto it : M)
        temp.push_back((int) it);




    vector<int> vec;
    for(int i=0;i<31;i++)
    {
    
        if(C[i]==0)
            vec.push_back(i);
    }
    for(int i=0;i<vec.size()-1;i++)
    {
        int br=vec[i+1]-vec[i];

        for(int j=0;j<br-1;j++)
        {
            R[j][vec[i]]=0;
        }
        R[br-1][vec[i]]=1;
    }
    int br=31+vec[0]-vec[vec.size()-1];
    for(int j=0;j<br-1;j++)
        {
            R[j][vec[vec.size()-1]]=0;
        }
        R[br-1][vec[vec.size()-1]]=1;
        int p=0;
        for(int i=0;i<R.size();i++)
        {
            for(int j=0;j<R[0].size();j++)
            {
                if(R[i][j]==-1 && C[j]==0)
                {
                    R[i][j]=temp[p];
                    p++;
                }
            }
        }
        for(auto it : R)
        {
            vector<bool> vecc;
            for(auto it2 : it)
            {
                vecc.push_back(it2);
            }
            send_packet(vecc);
        }

}

vector<int> adj[32];

void dfs(int i,int d,int& br,int og)
{
    if(i==og && d!=16 && d!=0)
    {
        return;
    }
    if(adj[i].size()==0)
        return;
    if(d==16)
    {
        if(og==i)
        {
            br=i;
            return;
        }
        return;
    }
    else
    {


        dfs(adj[i][0],d+1,br,og);

    }
}

void dfs2(int i,int og,vector<int>& vec,bool first)
{
    if(i==og && first==false)
        return;
    else
    {
        vec.push_back(i);
        dfs2(adj[i][0],og,vec,false);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R)
{
    for(int i=0;i<32;i++)
        adj[i].clear();
    bool arr[R.size()][R[0].size()];
    memset(arr,false,sizeof(arr));
    for(int i=0;i<R[0].size();i++)
    {
        for(int j=0;j<R.size();j++)
        {
            arr[j][i]=true;
            if(R[j][i]==1)
            {

                adj[i].push_back((i+j+1)%31);
                break;
            }
        }
    }

    vector<int> vec;

    for(int i=0;i<31;i++)
    {


        int br=-1;
        dfs(i,0,br,i);
        if(br!=-1)
        {

            dfs2(i,i,vec,true);
            break;
        }
    }


    bool vis[33]={};
    for(auto it : vec)
        vis[it]=true;
    vector<bool> temp;

    for(int i=0;i<R.size();i++)
    {
        for(int j=0;j<R[0].size();j++)
        {
            if(arr[i][j]!=true && vis[j]==true)
            {
                temp.push_back(R[i][j]);
            }
        }
    }

    bool b=false;
    vector<bool> res;
    for(auto it : temp)
    {
        if(b==true)
            res.push_back(it);
        if(it==1)
            b=true;
    }
    return res;


}

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