제출 #1320358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320358		hirayuu_oj	메시지 (IOI24_message)	C++20	100 / 100	438 ms	880 KiB

message

//#define _GLIBCXX_DEBUG
#include "message.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef pair<ll, ll> P;
using vs = vector<string>;
using vvs = vector<vs>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
#define lb(v, k) (lower_bound(all(v), (k)) - v.begin())
#define ub(v, k) (upper_bound(all(v), (k)) - v.begin())
#define fi first
#define se second
#define pb push_back
#define double long double
template <typename T>
bool chmax(T &a, const T &b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
template <typename T>
bool chmin(T &a, const T &b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
ll mod = 998244353;
ll inf = 999999999999999999LL;
/*struct union_find{
    int n;
    vl root;
    vl siz;
    vvl S;
    ll ans = 0;
    void init(int N){
        n = N;
        root.assign(N, -1);
        siz.assign(N, 1);
        S.assign(N, vl(5));
    }
    vl st;
    int leader(int p){
        while(root[p] != -1){
            st.pb(p);
            p = root[p];
        }
        for(auto x : st){
            root[x] = p;
        }
        st.clear();
        return p;
    }
    bool same(int p, int q){
        return (leader(p) == leader(q));
    }
    int merge(int p, int q){
        p = leader(p), q = leader(q);
        if(p != q){
            if(siz[p] < siz[q]){
                swap(p, q);
            }
            if(S[p][1] % 2 == 1){
            if(S[p][0] % 2 == 0){
                ans -= min(S[p][2], S[p][4]);
            }
            else{
                ans -= min(S[p][3], S[p][4]);
            }
            }
            if(S[q][1] % 2 == 1){
            if(S[q][0] % 2 == 0){
                ans -= min(S[q][2], S[q][4]);
            }
            else{
                ans -= min(S[q][3], S[q][4]);
            }
            }
            siz[p] += siz[q];
            chmin(S[p][0], S[q][0]);
            S[p][1] += S[q][1];
            chmin(S[p][2], S[q][2]);
            chmin(S[p][3], S[q][3]);
            chmin(S[p][4], S[q][4]);
            root[q] = p;
            if(S[p][1] % 2 == 1){
            if(S[p][0] % 2 == 0){
                ans += min(S[p][2], S[p][4]);
            }
            else{
                ans += min(S[p][3], S[p][4]);
            }
            }
        }
        return p;
    }
};*/
void send_message(std::vector<bool> M, std::vector<bool> C){
    M.pb(false);
    while(M.size() < 1025){
        M.pb(true);
    }
    vl F;
    rep(i, 31){
        if(!C[i]){
            F.pb(i);
        }
    }
    vector<vector<ll>> X(66, vl(31, -1));
    rep(i, 16){
        int p;
        if(i != 15){
            p = F[i + 1] - F[i];
        }
        else{
            p = F[0] + 31 - F[i];
        }
        rep(j, p - 1){
            X[j][F[i]] = 0;
        }
        X[p - 1][F[i]] = 1;
        //cout << p << ' ' << F[i] << endl;
    }
    int cnt = 0;
    rep(i, 66){
        rep(j, 31){
            if(C[j])continue;
            if(X[i][j] == -1){
                //cout << cnt << endl;
                if(M[cnt]){
                    X[i][j] = 1;
                }
                else{
                    X[i][j] = 0;
                }
                cnt++;
            }
        }
    }
            //cout << cnt << endl;
    rep(i, 66){
        vb A(31);
        rep(j, 31){
            if(X[i][j]){
                A[j] = true;
            }
            else{
                A[j] = false;
            }
        }
        send_packet(A);
    }
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
    vl F(31);
    rep(i, 31){
        while(!R[F[i]][i]){
            F[i]++;
            if(F[i] >= 40)break;
        }
        F[i]++;
        F[i] += i;
        F[i] %= 31;
    }
    vl ok;
    rep(i, 31){
        vb ch(31, false);
        ll p = i;
        vl g;
        rep(j, 16){
            p = F[p];
            if(ch[p])break;
            ch[p] = true;
            g.pb(p);
        }
        if(g.size() == 16){
            if(p == i){
                ok = g;
                break;
            }
        }
    }
    
    /*for(auto x : F){
        cout << x << ' ';
    }
    cout << endl;
    
    for(auto x : ok){
        cout << x << ' ';
    }
    cout << endl;*/
    vb C(31, true);
    for(auto x : ok){
        C[x] = false;
    }
    //
    
    vvl X(66, vl(31));
    rep(i, 66){
        rep(j, 31){
            if(R[i][j]){
                X[i][j] = 1;
            }
            else{
                X[i][j] = 0;
            }
        }
    }
    rep(i, 16){
        ll p = F[ok[i]] - ok[i];
        if(p < 0) p += 31;
        rep(j, p){
            X[j][ok[i]] = -1;
        }
        //cout << p << endl;
    }
    vl mess;
    //
    rep(i, 66){
        rep(j, 31){
            if(C[j])continue;
            if(X[i][j] == 1){
                mess.pb(1);
            }
            else if(X[i][j] == 0){
                mess.pb(0);
            }
        }
    }
    while(mess.back() == 1){
        mess.pop_back();
    }
    mess.pop_back();
    vb H;
    for(auto x : mess){
        if(x == 1){
            H.pb(true);
        }
        else{
            H.pb(false);
        }
    }
    return H;
}

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