Submission #946478

#	Time	Username	Problem	Language	Result	Execution time	Memory
946478		Nhoksocqt1	Alice, Bob, and Circuit (APIO23_abc)	C++17	12 / 100	126 ms	23272 KiB

abc

#ifndef Nhoksocqt1
    #include "abc.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
#define names ajfhqwurhuqerw
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 702;
const int MAXM = 1003;

string names[MAXN], letter[MAXM][2];
int n, m;

int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
    int lA(0);
    for (int j = 0; j < 16; ++j)
        outputs_alice[lA++] = (numbers[0] >> j & 1);

    outputs_alice[lA++] = 0;
    return lA;
    for (int i = 0; i < n; ++i) {
        bool check(0);
        for (int j = 0; j < 4; ++j) {
            int val = 26;
            if(!check)
                check |= (names[i][j] == '\0');

            if(!check)
                val = names[i][j] - 'a';

            for (int k = 4; k >= 0; --k)
                outputs_alice[lA++] = val >> k & 1;
        }

        for (int k = 15; k >= 0; --k)
            outputs_alice[lA++] = numbers[i] >> k & 1;
    }

    return lA;
}

int bob(const int m, const char send[][5], const char recei[][5], bool outputs_bob[]) {
    return m;
    int lB(0);
    for (int i = 0; i < m; ++i) {
        bool check(0);
        for (int j = 0; j < 4; ++j) {
            int val = 26;
            if(!check)
                check |= (send[i][j] == '\0');

            if(!check)
                val = send[i][j] - 'a';

            for (int k = 4; k >= 0; --k)
                outputs_bob[lB++] = val >> k & 1;
        }

        check = 0;
        for (int j = 0; j < 4; ++j) {
            int val = 26;
            if(!check)
                check |= (recei[i][j] == '\0');

            if(!check)
                val = recei[i][j] - 'a';

            for (int k = 4; k >= 0; --k)
                outputs_bob[lB++] = val >> k & 1;
        }
    }

    return lB;
}

int circuit(const int la, const int lb, int ope[], int gate[][2], int outputs_circuit[][16]) {
    int l(la + lb);
    for (int j = 0; j < 16; ++j) {
        ope[l] = 8;
        gate[l][0] = gate[l][1] = 16;
        ++l;
    }

    for (int t = 0; t < lb; ++t) {
        for (int j = 0; j < 16; ++j) {
            ope[l] = 8;
            gate[l][0] = gate[l][1] = j;
            ++l;
        }

        for (int j = 0; j < 16; ++j) {
            for (int t = 0; t < 16; ++t) {
                ope[l] = 6;
                gate[l][0] = l - 32, gate[l][1] = l - 16;
                ++l;
            }

            ope[l] = 8;
            gate[l][0] = gate[l][1] = 16;
            ++l;

            for (int t = 1; t < 16; ++t) {
                ope[l] = 8;
                gate[l][0] = l - 49, gate[l][1] = l - 33;
                ++l;
            }
        }

        for (int j = 0; j < 16; ++j) {
            ope[l] = 14;
            gate[l][0] = l - 32, gate[l][1] = l - 16;
            ++l;
        }
    }

    for (int i = 0; i < 16; ++i)
        outputs_circuit[0][i] = l - 16 + i;

    return l;
}

#ifdef Nhoksocqt1

int ope[100 * MAXM], gate[100 * MAXM][2], circuit_output[MAXN][16];
bool alice_output[100 * MAXM], bob_output[100 * MAXM], val[20000 * MAXM];

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "abc"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    unsigned short numbers[MAXN];
    char names[MAXN][5];
    char send[MAXM][5], reic[MAXM][5];
    int n, m;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < sz(str); ++j)
            names[i][j] = str[j];

        names[i][sz(str)] = '\0';
        cin >> numbers[i];
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        string sa, sb;
        cin >> sa >> sb;
        for (int j = 0; j < sz(sa); ++j)
            send[i][j] = sa[j];

        for (int j = 0; j < sz(sb); ++j)
            reic[i][j] = sb[j];

        send[i][sz(sa)] = reic[i][sz(sb)] = '\0';
    }

    int la = alice(n, names, numbers, alice_output);
    int lb = bob(m, send, reic, bob_output);
    int l = circuit(la, lb, ope, gate, circuit_output);
    for (int i = 0; i < la; ++i)
        val[i] = alice_output[i];

    for (int i = la; i < lb; ++i)
        val[i] = bob_output[i - la];

    for (int i = la + lb; i < l; ++i) {
        int x(gate[i][0]), y(gate[i][1]);
        if(ope[i] == 8) {
            val[i] = (val[x] & val[y]);
        } else
            if(ope[i] == 14) {
                val[i] = (val[x] | val[y]);
            } else
                if(ope[i] == 6) {
                    val[i] = (val[x] ^ val[y]);
                } else
                    if(ope[i] == 5) {
                        val[i] = !val[x];
                    } else {
                        abort();
                    }
    }

    for (int i = 0; i < n; ++i) {
        int res(0);
        for (int j = 0; j < 16; ++j)
            res |= val[circuit_output[i][j]] << j;

        cout << res << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 6
• Subtask 7: 0 / 18
• Subtask 8: 0 / 10
• Subtask 9: 0 / 6