oj.uz

Submission #1099953

# Submission time Handle Problem Language Result Execution time Memory
1099953 2024-10-12T08:05:37 Z ttamx Message (IOI24_message) C++17
100 / 100
 909 ms 1056 KB 
#include <bits/stdc++.h>
#include "message.h"

using namespace std;

const int B=31;
const int P=16;

void send_message(vector<bool> M,vector<bool> C){
    int tail=M.back()^1;
    M.emplace_back(tail);
    vector<int> pos;
    for(int i=0;i<B;i++){
        if(!C[i]){
            pos.emplace_back(i);
        }
    }
    vector<int> val(P);
    for(int i=0;i<P;i++){
        val[i]=(pos[(i+1)%P]-pos[i]+B)%B;
    }
    int cur=0;
    for(int i=0;i<B;i++){
        vector<bool> tmp(B);
        for(int j=0;j<P;j++){
            if(i<val[j]){
                if(i==val[j]-1){
                    tmp[pos[j]]=1;
                }
            }else{
                if(cur<M.size()){
                    tmp[pos[j]]=M[cur];
                    cur++;
                }else{
                    tmp[pos[j]]=tail;
                }
            }
        }
        send_packet(tmp);
    }
    while(cur<M.size()){
        vector<bool> tmp(B);
        for(auto x:pos){
            if(cur<M.size()){
                tmp[x]=M[cur];
                cur++;
            }else{
                tmp[x]=tail;
            }
        }
        send_packet(tmp);
    }
}

vector<bool> receive_message(vector<vector<bool>> R){
    vector<int> val(B);
    for(int i=B-1;i>=0;i--){
        for(int j=0;j<B;j++){
            if(R[i][j]){
                val[j]=i+1;
            }
        }
    }
    vector<int> nxt(B),deg(B);
    for(int i=0;i<B;i++){
        nxt[i]=(i+val[i])%B;
        deg[nxt[i]]++;
    }
    vector<bool> vis(B);
    queue<int> q;
    for(int i=0;i<B;i++){
        if(deg[i]==0){
            q.emplace(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=true;
        int v=nxt[u];
        deg[v]--;
        if(deg[v]==0){
            q.emplace(v);
        }
    }
    vector<int> pos;
    for(int i=0;i<B;i++){
        if(vis[i]){
            continue;
        }
        vector<int> cyc;
        for(int u=i;!vis[u];u=nxt[u]){
            vis[u]=true;
            cyc.emplace_back(u);
        }
        if(cyc.size()==P){
            swap(cyc,pos);
        }
    }
    assert(!pos.empty());
    vector<bool> ans;
    for(int i=0;i<R.size();i++){
        for(int j=0;j<P;j++){
            if(i>=val[pos[j]]){
                ans.emplace_back(R[i][pos[j]]);
            }
        }
    }
    int tail=ans.back();
    while(ans.back()==tail){
        ans.pop_back();
    }
    return ans;
}

Compilation message

message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 if(cur<M.size()){
      |                    ~~~^~~~~~~~~
message.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(cur<M.size()){
      |           ~~~^~~~~~~~~
message.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if(cur<M.size()){
      |                ~~~^~~~~~~~~
message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<R.size();i++){
      |                 ~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 31 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 816 KB Used 31 days
2 Correct 429 ms 800 KB Used 31 days
3 Correct 443 ms 800 KB Used 31 days
4 Correct 431 ms 1052 KB Used 31 days
5 Correct 350 ms 804 KB Used 31 days
6 Correct 224 ms 792 KB Used 31 days
7 Correct 281 ms 792 KB Used 31 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 31 days
2 Correct 412 ms 816 KB Used 31 days
3 Correct 429 ms 800 KB Used 31 days
4 Correct 443 ms 800 KB Used 31 days
5 Correct 431 ms 1052 KB Used 31 days
6 Correct 350 ms 804 KB Used 31 days
7 Correct 224 ms 792 KB Used 31 days
8 Correct 281 ms 792 KB Used 31 days
9 Correct 900 ms 796 KB Used 66 days
10 Correct 568 ms 820 KB Used 66 days
11 Correct 847 ms 800 KB Used 66 days
12 Correct 800 ms 816 KB Used 66 days
13 Correct 909 ms 816 KB Used 65 days
14 Correct 658 ms 1056 KB Used 66 days
15 Correct 541 ms 816 KB Used 66 days
16 Correct 682 ms 796 KB Used 66 days
17 Correct 691 ms 796 KB Used 66 days
18 Correct 476 ms 800 KB Used 31 days
19 Correct 442 ms 808 KB Used 31 days
20 Correct 434 ms 1056 KB Used 31 days
21 Correct 430 ms 1056 KB Used 31 days
22 Correct 481 ms 812 KB Used 34 days
23 Correct 429 ms 820 KB Used 40 days
24 Correct 545 ms 796 KB Used 46 days
25 Correct 620 ms 816 KB Used 52 days
26 Correct 773 ms 820 KB Used 59 days
27 Correct 804 ms 828 KB Used 65 days
28 Correct 782 ms 824 KB Used 66 days