Submission #922907

#	Time	Username	Problem	Language	Result	Execution time	Memory
922907		Pring	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	657 ms	427528 KiB

abc

#include <bits/stdc++.h>
// #include "abc.h"

using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

const int LEN = 16, MXC = 26;
const int MXN = 2048;

namespace STRING {
    const int FOOL = 524287;
    int CVT(string s) {
        int ans = 0;
        for (auto &i : s) ans = ans * MXC + (i - 'a');
        if (s.size() > 1) ans += MXC;
        if (s.size() > 2) ans += MXC * MXC;
        if (s.size() > 3) ans += MXC * MXC * MXC;
        return ans;
    }
}

struct P {
    int a, b, val, t;
    P() {}
    P(int _a, int _b, int _v, int _t) : a(_a), b(_b), val(_v), t(_t) {}
};

struct PP {
    int pa, pb, pv, pt;
    PP() {}
    PP(int _a, int _b, int _v, int _t) : pa(_a), pb(_b), pv(_v), pt(_t) {}
};

namespace PERMUTATION {
    string s;
    void PERM(vector<int> v, int dep) {
        int n = v.size();
        // cout << string(2 * dep, ' ') << n << ' ' << s.size() << endl;
        if (n == 1) return;
        int odd = n % 2;
        if (odd) v.push_back(n++);
        int x = n / 2;
        vector<pii> edge(n), e(x, mp(-1, -1));
        FOR(i, 0, n) {
            int id = v[i] % x;
            if (e[id].fs == -1) e[id].fs = i;
            else e[id].sc = i;
        }
        FOR(i, 0, x) {
            edge[i].fs = i + x;
            edge[i + x].fs = i;
            edge[e[i].fs].sc = e[i].sc;
            edge[e[i].sc].sc = e[i].fs;
        }
        vector<bool> b(n);
        vector<int> cyc;
        auto CYC = [&](int sr) {
            int p = sr, now = edge[sr].fs;
            b[p] = true;
            b[now] = true;
            cyc.push_back(p);
            cyc.push_back(now);
            while (true) {
                int nxt = (edge[now].fs ^ edge[now].sc ^ p);
                if (nxt == sr) break;
                b[nxt] = true;
                cyc.push_back(nxt);
                p = now;
                now = nxt;
            }
        };
        for (int i = x - 1; i >= 0; i--) {
            if (b[i]) continue;
            CYC(i);
        }
        string t(x, '0');
        for (int i = 0; i < n; i += 2) {
            if (cyc[i] >= x) {
                t[cyc[i] - x] ^= 1;
                swap(v[cyc[i]], v[cyc[i] - x]);
            }
        }
        if (odd) t.pop_back();
        // cout << t.size() << endl;
        s += t;
        vector<int> vl, vr;
        FOR(i, 0, x) vl.push_back(v[i] % x);
        FOR(i, x, n - odd) vr.push_back(v[i] % x);
        // cout << string(2 * dep, ' ') << vr.size() << endl;
        PERM(vl, dep + 1);
        PERM(vr, dep + 1);
        vector<pii> vpl, vpr;
        FOR(i, 0, x) vpl.push_back(mp(vl[i], v[i]));
        FOR(i, x, n - odd) vpr.push_back(mp(vr[i - x], v[i]));
        sort(vpl.begin(), vpl.end());
        sort(vpr.begin(), vpr.end());
        FOR(i, 0, vr.size()) s.push_back((vpl[i].sc > vpr[i].sc) ? '1' : '0');
        // cout << string(2 * dep, ' ') << n << ' ' << s.size() << endl;
    }
    string DO(vector<int> &a) {
        s.clear();
        PERM(a, 0);
        return s;
    }
}

int dp[MXN];

void LEN_INIT() {
    dp[0] = 0;
    dp[1] = 0;
    FOR(i, 2, MXN) {
        dp[i] = i / 2 * 2 + dp[i / 2] + dp[(i + 1) / 2];
    }
    // cout << "DP: ";
    // cout << dp[7] << endl;
}

int BSH_LEN(int x) {
    int l = 2, r = 2049;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        ((mid * 55 + dp[mid]) <= x ? l : r) = mid;
    }
    return l;
}

// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    vector<pair<P, int>> v(n);
    FOR(i, 0, n) v[i] = mp(P(STRING::CVT(string(names[i])), STRING::CVT(string(names[i])), numbers[i], 0), i);
    v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 0), n));
    v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 0), n + 1));
    int nn = v.size();
    sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
        return a.fs.a > b.fs.a;
    });
    vector<int> p;
    FOR(i, 0, nn) p.push_back(v[i].sc);
    string s = PERMUTATION::DO(p);
    int cnt = 0;
    auto PUT = [&](int x, int len) {
        FOR(i, 0, len) {
            outputs_alice[cnt] = ((x & (1 << i)) ? 1 : 0);
            cnt++;
        }
    };
    FOR(i, 0, nn) {
        PUT(v[i].fs.a, 19);
        PUT(v[i].fs.b, 19);
        PUT(v[i].fs.val, LEN);
        PUT(v[i].fs.t, 1);
    }
    // cout << s.size() << endl;
    for (auto &i : s) {
        outputs_alice[cnt] = (i & 1);
        cnt++;
    }
    return cnt;
}

// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    vector<pair<P, int>> v(m);
    FOR(i, 0, m) v[i] = mp(P(STRING::CVT(string(senders[i])), STRING::CVT(recipients[i]), 0, 1), 0);
    v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 1), 0));
    v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 1), 0));
    int mm = v.size();
    sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
        return a.fs.b < b.fs.b;
    });
    FOR(i, 0, mm) v[i].sc = i;
    sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
        return a.fs.a < b.fs.a;
    });
    vector<int> p;
    FOR(i, 0, mm) p.push_back(v[i].sc);
    string s = PERMUTATION::DO(p);
    int cnt = 0;
    auto PUT = [&](int x, int len) {
        FOR(i, 0, len) {
            outputs_bob[cnt] = ((x & (1 << i)) ? 1 : 0);
            cnt++;
        }
    };
    FOR(i, 0, mm) {
        PUT(v[i].fs.a, 19);
        PUT(v[i].fs.b, 19);
        PUT(v[i].fs.val, LEN);
        PUT(v[i].fs.t, 1);
    }
    for (auto &i : s) {
        outputs_bob[cnt] = (i & 1);
        cnt++;
    }
    return cnt;
}

// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {

    LEN_INIT();
    int na = BSH_LEN(la), nb = BSH_LEN(lb);
    int cnt = la + lb;
    int sa = na * 55, sb = la + nb * 55;

    vector<PP> v;
    FOR(i, 0, na) v.push_back(PP(0  + i * 55 + 0, 0  + i * 55 + 19, 0  + i * 55 + 38, 0  + i * 55 + 54));
    FOR(i, 0, nb) v.push_back(PP(la + i * 55 + 0, la + i * 55 + 19, la + i * 55 + 38, la + i * 55 + 54));

    P msk1 = P(1, 0, 0, 1), msk2 = P(0, 1, 0, 1);
    vector<int> cmp_bit;

    auto add_op = [&](int input_a, int input_b, int op) {
        operations[cnt] = op;
        operands[cnt][0] = input_a, operands[cnt][1] = input_b;
        return cnt++;
    };

    auto add_ops = [&](int inputs_a, int inputs_b, int op, int len) {
        int pos = cnt;
        FOR(i, 0, len) {
            add_op(inputs_a + i, inputs_b + i, op);
        }
        return pos;
    };

    auto add_op_obj = [&](PP a, PP b, int op) {
        int pos = cnt;
        FOR(i, 0, 19) add_op(a.pa + i, b.pa + i, op);
        FOR(i, 0, 19) add_op(a.pb + i, b.pb + i, op);
        FOR(i, 0, LEN) add_op(a.pv + i, b.pv + i, op);
        FOR(i, 0, 1) add_op(a.pt + i, b.pt + i, op);
        return PP(pos + 0, pos + 19, pos + 38, pos + 54);
    };

    auto add_op_1 = [&](int inputs_a, int input_b, int op, int len) {
        int pos = cnt;
        FOR(i, 0, len) {
            add_op(inputs_a + i, input_b, op);
        }
        return pos;
    };

    auto add_op_obj_1 = [&](PP a, int b, int op) {
        int pos = cnt;
        FOR(i, 0, 19) add_op(a.pa + i, b, op);
        FOR(i, 0, 19) add_op(a.pb + i, b, op);
        FOR(i, 0, LEN) add_op(a.pv + i, b, op);
        FOR(i, 0, 1) add_op(a.pt + i, b, op);
        return PP(pos + 0, pos + 19, pos + 38, pos + 54);
    };

    while (v.size() != 2048) {
        v.push_back(PP(add_ops(0, 0, OP_ONE, 19), add_ops(0, 0, OP_ONE, 19), add_ops(0, 0, OP_ZERO, LEN), add_op(0, 0, OP_ONE)));
    }

    auto adder = [&](int inputs_a, int inputs_b, int len) {
        int c = 54, c1, c2, g1;
        vector<int> vc, vg;
        FOR(i, 0, len) {
            int a = inputs_a + i, b = inputs_b + i;
            c1 = add_op(a, b, OP_AND);
            g1 = add_op(a, b, OP_XOR);
            c2 = add_op(c, g1, OP_AND);
            vc.push_back(c);
            vg.push_back(g1);
            c = add_op(c1, c2, OP_OR);
        }
        int pos = cnt;
        FOR(i, 0, len) {
            add_op(vg[i], vc[i], OP_XOR);
        }
        return pos;
    };

    auto CMP = [&](PP a, PP b, P mask) {
        int p = 54;
        if (mask.t) {
            FOR(i, 0, 1) {
                int l = a.pt + i, r = b.pt + i;
                int s = add_op(l, r, OP_XOR);
                p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
            }
        }
        if (mask.b) {
            FOR(i, 0, 19) {
                int l = a.pb + i, r = b.pb + i;
                int s = add_op(l, r, OP_XOR);
                p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
            }
        }
        if (mask.a) {
            FOR(i, 0, 19) {
                int l = a.pa + i, r = b.pa + i;
                int s = add_op(l, r, OP_XOR);
                p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
            }
        }
        return p;
    };

    auto SWAP = [&](int &a, int &b, int s, int len) {
        int x = add_op_1(a, s, OP_GREATER, len), y = add_op_1(b, s, OP_AND, len);
        int c = add_ops(x, y, OP_OR, len);
        int d = add_ops(c, a, OP_XOR, len);
        int e = add_ops(d, b, OP_XOR, len);
        a = c, b = e;
    };

    auto SWAP_OBJ = [&](PP &a, PP &b, int s) {
        PP x = add_op_obj_1(a, s, OP_GREATER), y = add_op_obj_1(b, s, OP_AND);
        PP c = add_op_obj(x, y, OP_OR);
        PP d = add_op_obj(c, a, OP_XOR);
        PP e = add_op_obj(d, b, OP_XOR);
        a = c, b = e;
    };

    auto bitonic_sort = [&](auto self, int l, int r, P mask) {
        if (l + 1 == r) return;
        int x = (r - l) >> 1;
        FOR(i, 0, x) {
            cmp_bit.push_back(CMP(v[l + i], v[l + x + i], mask));
            SWAP_OBJ(v[l + i], v[l + x + i], cmp_bit.back());
        }
        self(self, l, l + x, mask);
        self(self, l + x, r, mask);
    };

    auto bitonic_undo = [&](auto self, int l, int r) {
        if (l + 1 == r) return;
        int x = (r - l) >> 1;
        self(self, l + x, r);
        self(self, l, l + x);
        for (int i = x - 1; i >= 0; i--) {
            SWAP_OBJ(v[l + i], v[l + x + i], cmp_bit.back());
            cmp_bit.pop_back();
        }
    };

    auto SHIFT = [&](auto self, int l, int r, int s, int &ptr) {
        if (l + 1 == r) return;
        int n = r - l;
        int x = n >> 1;
        int mid = l + x + (n & 1);
        FOR(i, 0, x) {
            SWAP_OBJ(v[l + i], v[mid + i], s + ptr);
            ptr++;
        }
        self(self, l, mid, s, ptr);
        self(self, mid, r, s, ptr);
        FOR(i, 0, x) {
            SWAP_OBJ(v[l + i], v[mid + i], s + ptr);
            ptr++;
        }
    };

    auto SWEEP1 = [&]() {
        int x = add_op_1(0, 0, OP_ZERO, LEN);
        FOR(i, 0, MXN) {
            int &val = v[i].pv, s = v[i].pt;
            int tmp = add_ops(add_op_1(x, s, OP_AND, LEN), add_op_1(val, s, OP_GREATER, LEN), OP_OR, LEN);
            int tmp2 = add_ops(tmp, tmp, OP_AND, LEN);
            x = tmp, val = tmp2;
        }
    };

    auto SWEEP2 = [&]() {
        int x = add_op_1(0, 0, OP_ZERO, LEN);
        FOR(i, 0, MXN) {
            int &val = v[i].pv, s = v[i].pt;
            val = add_op_1(val, s, OP_AND, LEN);
            SWAP(x, val, s, LEN);
            val = adder(x, val, LEN);
            x = add_op_1(x, 0, OP_ZERO, LEN);
            SWAP(x, val, s, LEN);
        }
    };

    bitonic_sort(bitonic_sort, 0, MXN, msk1);
    SWEEP1();
    bitonic_undo(bitonic_undo, 0, MXN);
    int ptr = 0;
    SHIFT(SHIFT, na, na + nb, sb, ptr);
    FOR(i, 0, MXN) {
        int &id = v[i].pt;
        id = add_op(id, 0, OP_NOT_X0);
    }
    bitonic_sort(bitonic_sort, 0, MXN, msk2);
    FOR(i, 0, MXN) {
        int &id = v[i].pt;
        id = add_op(id, 0, OP_NOT_X0);
    }
    SWEEP2();
    bitonic_undo(bitonic_undo, 0, MXN);
    ptr = 0;
    SHIFT(SHIFT, 0, 0 + na, sa, ptr);

    FOR(i, 0, na - 2) {
        int id = v[i].pv;
        FOR(j, 0, LEN) outputs_circuit[i][j] = id + j;
    }
    return cnt;
}

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