제출 #1157212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157212		erering	메시지 (IOI24_message)	C++20	72.85 / 100	395 ms	884 KiB

message

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#include "message.h"

void send_message(vector<bool> M, vector<bool> C) {
    vector<vector<bool>> A(4,vector<bool>(31));
    int x=0,pos[17];
    vector<int> gd;
    for(int i=0;i<31;i++){
        if(!C[i]){
            int rep=x;
            for(int j=0;j<4;j++){
                A[j][i]=rep%2;
                rep/=2;
            }
            pos[x]=i;
            gd.pb(i);
            x++;
        }
        else{
            for(int j=0;j<4;j++)A[j][i]=0;
        }
    }
    vector<bool> edited[4];
    for(int i=0;i<4;i++){
        edited[i]=send_packet(A[i]);
    }
    vector<int> am[17];
    for(int i=0;i<31;i++){
        x=0;
        for(int j=3;j>=0;j--){
            x*=2;
            if(edited[j][i])x++;
        }
        am[x].pb(i);
    }
    vector<int> known;
    vector<pair<int,int>>  unknown;
    vector<vector<bool>> vec;
    for(int i=0;i<16;i++){
        if(am[i].size()==1)known.pb(am[i][0]);
        else unknown.pb({am[i].size(),i});
    }
    sort(known.begin(),known.end());
    sort(unknown.begin(),unknown.end());
    vector<bool> nd;
    vector<int> willknow;
    for(int i=0;i<unknown.size();i++){
        int cnt=0;
        x=1;
        while(x<unknown[i].first){
            x*=2;
            cnt++;
        }
        int req=pos[unknown[i].second];
        for(int j=0;j<am[unknown[i].second].size();j++){
            if(am[unknown[i].second][j]==pos[unknown[i].second]){
                req=j;
                break;
            }
        }
        string s;
        for(int j=0;j<cnt;j++){
            if(req%2)s+='1';
            else s+='0';
            req/=2;
            if(j==cnt-1)willknow.pb(pos[unknown[i].second]);
            else willknow.pb(-1);
        }
        reverse(s.begin(),s.end());
        for(int j=0;j<s.size();j++)nd.pb(s[j]=='1');
    }
    int l=0;
    vector<bool> message(31,0);
    vector<int> ready;
    for(int i=0;i<nd.size();i++){
        message[known[l]]=nd[i];
        if(willknow[i]!=-1)ready.pb(willknow[i]);
        l++;
        if(l==known.size() || i==nd.size()-1){
            send_packet(message);
            l=0;
            for(int j=0;j<ready.size();j++)known.pb(ready[j]);
            ready.clear();
            sort(known.begin(),known.end());
        }
    }
    l=0;
    for(int i=0;i<M.size();i++){
        message[known[l]]=M[i];
        l++;
        if(l==known.size() || i==M.size()-1){
            l=0;
            send_packet(message);
        }
    }
    int sz=M.size();
    for(int i=0;i<message.size();i++)message[i]=0;
    for(int i=known.size()-1;i>=0;i--){
        if(sz%2)message[known[i]]=1;
        sz/=2;
    }
    send_packet(message);
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int x;
    vector<int> am[17];
    for(int i=0;i<31;i++){
        x=0;
        for(int j=3;j>=0;j--){
            x*=2;
            if(R[j][i])x++;
        }
        am[x].pb(i);
    }
    vector<int> known;
    vector<pair<int,int>>  unknown;
    vector<vector<bool>> vec;
    for(int i=0;i<16;i++){
        if(am[i].size()==1)known.pb(am[i][0]);
        else unknown.pb({am[i].size(),i});
    }
    sort(known.begin(),known.end());
    sort(unknown.begin(),unknown.end());
    vector<bool> nd;
    int l=4,crnt=0,last=known.size();
    for(int i=0;i<unknown.size();i++){
        int cnt=0,cnt2=0;
        x=1;
        while(x<unknown[i].first){
            x*=2;
            cnt++;
        }
        x=0;
        while(cnt2<cnt){
            x*=2;
            if(R[l][known[crnt]])x++;
            cnt2++; crnt++;
            if(crnt==last){
                l++;
                crnt=0;
                last=known.size();
                sort(known.begin(),known.end());
            }
        }
        known.pb(am[unknown[i].second][x]);
        if(crnt==0 || i==unknown.size()-1){
            last=known.size();
            sort(known.begin(),known.end());
        }
    }
    vector<bool> ans;
    int sz=0;
    for(int i=0;i<known.size();i++){
        sz*=2;
        if(R[R.size()-1][known[i]]){
            sz++;
        }
    }
    if(crnt!=0)l++;
    for(int i=l;i<R.size();i++){
        for(int j=0;j<known.size() && ans.size()<sz;j++)ans.pb(R[i][known[j]]);
    }
    return ans;
}

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