Submission #1190321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190321		NotLinux	Message (IOI24_message)	C++20	34.97 / 100	613 ms	872 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l , int r){
    return rng() % (r-l+1) + l;
}
long long decipher = 0;
long long cur = 120397273ll;
long long sabit = 893721095ll;
const long long mod = 1e9 + 7;
const long long epoch = 25;
void init(){
    decipher = 0;
    cur = 120397273ll;
    sabit = 893721095ll;
}
int nxt(){
    cur = (cur * decipher + sabit) % mod;
    decipher = (decipher * sabit) % mod;
    sabit = (sabit + decipher) % mod;
    return cur & 1;
}
vector<vector<int>>dizi(epoch , vector<int>(31,0));
void send_message(vector<bool> M, vector<bool> C) {
    init();
    // decipheri belirle
    vector<bool>vec(31,0);
    for(int i = 0;i<31;i++)vec[i] = rand(0,1);
    vector<bool>v1 = send_packet(vec);
    decipher = 0;
    for(int i = 0;i<31;i++){
        if(v1[i]){
            decipher += 1ll << i;
        }
    }
    // kleopatralari bul
    for(int i = 0;i<epoch;i++){
        vec.assign(31,0);
        for(int j = 0;j<31;j++){
            if(C[j] == 0){
                vec[j] = nxt();
            }
            else{
                vec[j] = rand(0,1);
                nxt();
            }
        }
        send_packet(vec);
    }
    vec.assign(31,0);
    // mesajin uzunlugunu da yollamak lazim
    int len = M.size();
    for(int i = 0;i<11;i++){
        M.insert(M.begin() + i , len & (1ll << i));
    }
    // mesaji yolla
    int sayac = 0;
    for(int i = 0;i<(int)M.size();i++){
        while(C[sayac]){
            sayac = (sayac + 1) % 31;
            if(sayac == 0){
                send_packet(vec);
                vec.assign(31,0);
            }
        }
        vec[sayac] = M[i];
        sayac = (sayac + 1) % 31;
        if(sayac == 0){
            send_packet(vec);
            vec.assign(31,0);
        }
    }
    if(sayac != 0){
        send_packet(vec);
        vec.assign(31,0);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    init();
    // decipheri bul
    for(int i = 0;i<31;i++){
        if(R[0][i]){
            decipher += 1ll << i;
        }
    }
    // kleopatralari bul
    vector<bool>cleo(31,0);
    for(int i = 1;i<=epoch;i++){
        for(int j = 0;j<31;j++){
            if(R[i][j] != nxt()){
                cleo[j] = 1;
            }
        }
    }
    // mesajin uzunlugunu bul
    int sayac = 0 , mindx = epoch+1 , len = 0;
    for(int i = 0;i<11;i++){
        while(cleo[sayac]){
            sayac = (sayac + 1) % 31;
            if(sayac == 0)mindx++;
        }
        if(R[mindx][sayac])len += 1 << i;
        sayac = (sayac + 1) % 31;
        if(sayac == 0)mindx++;
    }
    // mesaji bul
    vector<bool>ret(len);
    for(int i = 0;i<len;i++){
        while(cleo[sayac]){
            sayac = (sayac + 1) % 31;
            if(sayac == 0)mindx++;
        }
        ret[i] = R[mindx][sayac];
        sayac = (sayac + 1) % 31;
        if(sayac == 0)mindx++;
    }
    return ret;
}

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