제출 #1166991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166991		Sang	Message (IOI24_message)	C++20	0 / 100	348 ms	840 KiB

message

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

vector<bool> send_packet(vector<bool> A);

void send_message(vector<bool> M, vector<bool> C){
    vector<int> d(35, 0);
    int last = -1;
    int s = 0;
    FOR (i, 0, 30){
        if (C[i]) continue;
        if (last != -1){
            d[last] = i - last;
            s += i - last;
        }
        last = i;
    }
    FOR (i, 0, 30){
        if (C[i] == 0){
            d[last] = i + 31 - last;
            s += i + 31 - last;
            break;
        }
    }
    assert(s == 31);
    last = M.back();
    FOR (i, 1, 66){
        vector<bool> packet;
        FOR (j, 0, 30){
            if (C[j] || d[j] > i) {
                packet.pb(0);
                continue;
            }
            if (d[j] == i){
                packet.pb(1);
                continue;
            }
            packet.pb((!M.empty() ? M.back() : (last ^ 1)));
            if (!M.empty()){
                last = M.back();
                M.pop_back();
            }
        }

        send_packet(packet);
    }
}

vector<bool> receive_message(vector<vector<bool>> R){
    vector<int> d(35, 0);
    FOR (i, 0, 29){
        FOR (j, 0, 30){
            if (d[j] || R[i][j] == 0)  continue;
            d[j] = i + 1;
        }
    }
    vector<int> good(35, 0);
    FOR (i, 0, 30){
        int j = i;
        while (d[j] && j + d[j] <= 30){
            j += d[j];
        }
        if ((j + d[j])%31 != i){
            continue;
        }
        j = i;
        while (d[j] && j + d[j] <= 30){
            good[j] = 1;
            j += d[j];
        }
        good[j] = 1;
        break;
    }

    vector<bool> ans;
    FOR (i, 0, 65){
        FOR (j, 0, 30){
            if (!good[j]) continue;
            if (i + 1 <= d[j]) continue;
            ans.pb(R[i][j]);
         }
    }

    int last = ans.back();
    while (!ans.empty() && ans.back() == last) ans.pop_back();
    //assert(!ans.empty());
    reverse(ALL(ans));
    return ans;
}

#ifdef _Pbrngw_
vector<vector<bool>> R;
vector<bool> send_packet(vector<bool> A){
    assert(A.size() == 31);
    R.pb(A);
    return A;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    send_message({0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0});
    vector<bool> ans = receive_message(R);
    for (bool x : ans) cout << x;

    return 0;
}
#endif // _Pbrngw_

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