제출 #1200706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200706		Pacybwoah	메시지 (IOI24_message)	C++20	51.70 / 100	458 ms	864 KiB

message

#include "message.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
    const int K = 8;
}

void send_message(std::vector<bool> M, std::vector<bool> C){
    vector<int> cnt(4);
    int s = (int)M.size(), n = 31;
    for(int i = 0; i < n; i++){
        if(C[i] == 0) cnt[i % 4]++;
    }
    int best = 0;
    for(int i = 1; i < 4; i++){
        if(cnt[i] > cnt[best]) best = i;
    }
    vector<bool> que(n);
    auto send = [&](bool flag){
        for(int i = 0; i < n; i++) que[i] = flag;
        send_packet(que);
        return;
    };
    send(best & 1);
    send(best >= 2);
    for(int i = best; i < n; i += 4){
        send(!C[i]);
    }
    fill(que.begin(), que.end(), 0);
    vector<int> rest, imp;
    for(int i = 0; i < n; i++){
        if(i % 4 != best) rest.push_back(i);
        else{
            if(!C[i]) imp.push_back(i);
        }
    }
    int sz = (int)rest.size();
    for(int i = 0; i < sz; i += cnt[best]){
        fill(que.begin(), que.end(), 0);
        for(int j = 0; j < cnt[best] && i + j < sz; j++){
            que[imp[j]] = (!C[rest[i + j]]);
        }
        send_packet(que);
    }
    int rem = s % 16;
    vector<int>().swap(imp);
    for(int i = 0; i < n; i++) if(!C[i]) imp.push_back(i);
    for(int i = 0; i < s; i += 16){
        fill(que.begin(), que.end(), 0);
        for(int j = 0; j < 16 && i + j < s; j++){
            que[imp[j]] = M[i + j];
        }
        send_packet(que);
    }
    fill(que.begin(), que.end(), 0);
    for(int j = 0; j < 4; j++){
        if(rem & (1 << j)) que[imp[j]] = 1;
        else que[imp[j]] = 0;
    }
    send_packet(que);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
    int best = 0;
    auto calc = [&](vector<bool>& vec){
        int sum = 0;
        int sz = (int)vec.size();
        for(int i = 0; i < sz; i++) if(vec[i]) sum++;
        if(sum < 16) return int(0);
        else return int(1);
    };  
    best += calc(R[0]) * 1;
    best += calc(R[1]) * 2;
    int cur = 2;
    int n = 31;
    vector<int> good(n), un, imp;
    int k = 0;
    for(int i = 0; i < n; i++){
        if(i % 4 == best){
            good[i] = calc(R[cur]);
            cur++;
            if(good[i]) k++, imp.push_back(i);
        }
        else un.push_back(i);
    }
    int sz = (int)un.size();
    for(int i = 0; i < sz; i += k){
        for(int j = 0; j < k && i + j < sz; j++){
            good[un[i + j]] = R[cur][imp[j]];
        }
        cur++;
    }
    vector<bool> ans;
    vector<int>().swap(imp);
    for(int i = 0; i < n; i++) if(good[i]) imp.push_back(i);
    int pus = (int)R.size();
    while(cur < pus - 1){
        for(int i = 0; i < 16; i++) ans.push_back(R[cur][imp[i]]);
        cur++;
    }
    int rem = 0;
    for(int i = 0; i < 4; i++) if(R[cur][imp[i]]) rem += (1 << i);
    if(rem > 0){
        for(int i = 0; i < 16 - rem; i++) ans.pop_back();
    }
    return ans;
}

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