Submission #946588

#	Time	Username	Problem	Language	Result	Execution time	Memory
946588		Nhoksocqt1	Alice, Bob, and Circuit (APIO23_abc)	C++17	48 / 100	97 ms	44408 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;

map<string, string> Map;
string names[MAXN], letter[MAXM][2];
int ans[MAXN][16], tmp[16], n, m;
int isSend[MAXN][MAXM], isRecei[MAXN][MAXM], ok[MAXN][MAXN];

int alice(const int n, const char str[][5], const unsigned short numbers[], bool outputs_alice[]) {
    Map.clear();
    vector<string> vString;
    for (int i = 0; i < n; ++i) {
        names[i].clear();
        for (int j = 0; j < 5; ++j) {
            if(str[i][j] == '\0')
                break;

            names[i].push_back(str[i][j]);
        }

        vString.push_back(names[i]);
    }

    sort(vString.begin(), vString.end());
    vString.erase(unique(vString.begin(), vString.end()), vString.end());

    int cnt(0);
    for (int it = 0; it < sz(vString); ++it) {
        string str(vString[it]);
        if(Map.find(str) == Map.end()) {
            string tmp;
            if(cnt >= 26) {
                tmp = "a" + char(cnt % 26 + 'a');
            } else {
                tmp = char(cnt + 'a');
            }

            Map[str] = tmp;
            str = tmp;
            ++cnt;
        }
    }

    for (int i = 0; i < n; ++i)
        names[i] = Map[names[i]];

    int lA(0);
    outputs_alice[lA++] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < sz(names[i]); ++j) {
            int val = names[i][j] - 'a';
            for (int k = 0; k < 16; ++k)
                outputs_alice[lA++] = val >> k & 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < 16; ++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[]) {
    Map.clear();
    vector<string> vString;
    for (int i = 0; i < m; ++i) {
        letter[i][0].clear();
        letter[i][1].clear();
        for (int j = 0; j < 5; ++j) {
            if(send[i][j] == '\0')
                break;

            letter[i][0].push_back(send[i][j]);
        }

        for (int j = 0; j < 5; ++j) {
            if(recei[i][j] == '\0')
                break;

            letter[i][1].push_back(recei[i][j]);
        }

        vString.push_back(letter[i][0]);
        vString.push_back(letter[i][1]);
    }

    sort(vString.begin(), vString.end());
    vString.erase(unique(vString.begin(), vString.end()), vString.end());

    int cnt(0);
    for (int it = 0; it < sz(vString); ++it) {
        string str(vString[it]);
        if(Map.find(str) == Map.end()) {
            string tmp;
            if(cnt >= 26) {
                tmp = "a" + char(cnt % 26 + 'a');
            } else {
                tmp = char(cnt + 'a');
            }

            Map[str] = tmp;
            str = tmp;
            ++cnt;
        }
    }

    for (int i = 0; i < m; ++i) {
        letter[i][0] = Map[letter[i][0]];
        letter[i][1] = Map[letter[i][1]];
    }

    int lB(0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < sz(letter[i][0]); ++j) {
            int val = letter[i][0][j] - 'a';
            for (int k = 0; k < 5; ++k)
                outputs_bob[lB++] = val >> k & 1;
        }

        for (int j = 0; j < sz(letter[i][1]); ++j) {
            int val = letter[i][1][j] - 'a';
            for (int k = 0; k < 5; ++k)
                outputs_bob[lB++] = val >> k & 1;
        }
    }

    return lB;
}

#ifdef Nhoksocqt1
bool alice_output[100 * MAXM], bob_output[100 * MAXM], val[20000 * MAXM];
#endif // Nhoksocqt1

int circuit(const int la, const int lb, int ope[], int gate[][2], int outputs_circuit[][16]) {
    int l(la + lb), n = (la - 1) / 16 / 2, m = lb / 2 / 5;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < 5; ++k) {
            ope[l] = 5;
            gate[l][0] = gate[l][1] = i * 16 + 1 + k;
            ++l;
        }
    }

    for (int j = 0; j < 16; ++j) {
        ope[l] = 8;
        gate[l][0] = gate[l][1] = 0;
        for (int i = 0; i < n; ++i)
            ans[i][j] = l;

        ++l;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int lst(-1);
            for (int k = 0; k < 5; ++k) {
                ope[l] = 6;
                gate[l][0] = la + lb + i * 5 + k, gate[l][1] = la + j * 10 + k;
                ++l;

                if(lst >= 0) {
                    ope[l] = 8;
                    gate[l][0] = lst, gate[l][1] = l - 1;
                    ++l;
                }

                lst = l - 1;
            }

            isSend[i][j] = lst;

            lst = -1;
            for (int k = 0; k < 5; ++k) {
                ope[l] = 6;
                gate[l][0] = la + lb + i * 5 + k, gate[l][1] = la + j * 10 + 5 + k;
                ++l;

                if(lst >= 0) {
                    ope[l] = 8;
                    gate[l][0] = lst, gate[l][1] = l - 1;
                    ++l;
                }

                lst = l - 1;
            }

            isRecei[i][j] = lst;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int lst(-1);
            for (int k = 0; k < m; ++k) {
                ope[l] = 8;
                gate[l][0] = isSend[j][k], gate[l][1] = isRecei[i][k];
                ++l;

                if(lst >= 0) {
                    ope[l] = 14;
                    gate[l][0] = lst, gate[l][1] = l - 1;
                    ++l;
                }

                lst = l - 1;
            }

            ok[i][j] = lst;
            for (int k = 0; k < 16; ++k) {
                ope[l] = 8;
                gate[l][0] = ok[i][j], gate[l][1] = (n + j) * 16 + 1 + k;
                tmp[k] = l;
                ++l;
            }

            for (int j = 0; j < 16; ++j) {
                int newa1[16], newa2[16];
                for (int t = 0; t < 16; ++t) {
                    ope[l] = 6;
                    gate[l][0] = ans[i][t], gate[l][1] = tmp[t];
                    newa1[t] = l;
                    ++l;
                }

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

                for (int t = 1; t < 16; ++t) {
                    ope[l] = 8;
                    gate[l][0] = ans[i][t - 1], gate[l][1] = tmp[t - 1];
                    newa2[t] = l;
                    ++l;
                }

                for (int j = 0; j < 16; ++j)
                    ans[i][j] = newa1[j], tmp[j] = newa2[j];
            }

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

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 16; ++j)
            outputs_circuit[i][j] = ans[i][j];
    }

    return l;
}

#ifdef Nhoksocqt1

int ope[100 * MAXM], gate[100 * MAXM][2], circuit_output[MAXN][16];

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 < la + lb; ++i)
        val[i] = bob_output[i - la];

    cout << "ALICE: " << la << '\n';
    for (int it = 0; it < la; ++it)
        cout << val[it] << ' '; cout << '\n';

    cout << "BOB: " << lb << '\n';
    for (int it = 0; it < lb; ++it)
        cout << val[la + it] << ' '; cout << '\n';

    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';
    }

    cout << "OK:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cout << val[ok[i][j]] << ' '; cout << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

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