Submission #765559

#	Time	Username	Problem	Language	Result	Execution time	Memory
765559		pandapythoner	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	1707 ms	1397656 KiB

abc

#include "abc.h"
// 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

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int bts = 16;
const int name_bts = 19;

int encode_name(const char *name) {
    int rs = 0;
    int t = 1;
    for (int len = 1;; len += 1) {
        t *= 26;
        if (name[len] == 0) {
            ll f = 0;
            for (int i = 0; i < len; i += 1) {
                f = f * 26 + (name[i] - 'a');
            }
            rs += f;
            break;
        }
        rs += t;
    }
    return rs;
}

// Alice
int  // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]) {
    if (n == 0) {
        outputs_alice[0] = 0;
        return 1;
    }
    int sz = n * (name_bts + bts);
    int t = 0;
    vector<pair<int, int>> srtd(n);
    for (int i = 0; i < n; i += 1) {
        int e = encode_name(names[i]);
        int num = numbers[i];
        srtd[i] = make_pair(e, num);
    }
    // sort(srtd.begin(), srtd.end());
    for (int i = 0; i < n; i += 1) {
        int e = srtd[i].first;
        for (int j = 0; j < name_bts; j += 1) {
            outputs_alice[t + j] = ((e >> j) & 1);
        }
        t += name_bts;
    }
    for (int i = 0; i < n; i += 1) {
        int e = srtd[i].second;
        for (int j = 0; j < bts; j += 1) {
            outputs_alice[t + j] = ((e >> j) & 1);
        }
        t += bts;
    }
    return sz;
}

// Bob
int  // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]) {
    int sz = m * (name_bts + name_bts);
    int t = 0;
    vector<pair<int, int>> srtd(m);
    for (int i = 0; i < m; i += 1) {
        int sndr = encode_name(senders[i]);
        int rcpnt = encode_name(recipients[i]);
        srtd[i] = make_pair(sndr, rcpnt);
    }
    sort(srtd.begin(), srtd.end());
    for (int i = 0; i < m; i += 1) {
        int e = srtd[i].first;
        for (int j = 0; j < name_bts; j += 1) {
            outputs_bob[t + j] = ((e >> j) & 1);
        }
        t += name_bts;
    }
    for (int i = 0; i < m; i += 1) {
        int e = srtd[i].second;
        for (int j = 0; j < name_bts; j += 1) {
            outputs_bob[t + j] = ((e >> j) & 1);
        }
        t += name_bts;
    }
    return sz;
}

vector<int> operator+(const vector<int> &a, const vector<int> &b) {
    vector<int> c;
    for (auto x : a) {
        c.push_back(x);
    }
    for (auto x : b) {
        c.push_back(x);
    }
    return c;
}

int c = 0;
vector<int> operations;
vector<vector<int>> operands;

int add_operation(int op_type, int op1, int op2) {
    operations.push_back(op_type);
    operands.push_back(vector<int>({op1, op2}));
    c += 1;
    return c - 1;
}

int check_equal(vector<int> a, vector<int> b) {
    int d = add_operation(OP_XOR, a[0], b[0]);
    for (int i = 1; i < (int)a.size(); i += 1) {
        int t = add_operation(OP_XOR, a[i], b[i]);
        d = add_operation(OP_OR, d, t);
    }
    d = add_operation(OP_NOT_X0, d, d);
    return d;
}

vector<int> get_if_equal(vector<int> a, vector<int> b, vector<int> num) {
    int d = add_operation(OP_XOR, a[0], b[0]);
    for (int i = 1; i < (int)a.size(); i += 1) {
        int t = add_operation(OP_XOR, a[i], b[i]);
        d = add_operation(OP_OR, d, t);
    }
    d = add_operation(OP_NOT_X0, d, d);
    vector<int> rs(num.size());
    for (int i = 0; i < (int)num.size(); i += 1) {
        rs[i] = add_operation(OP_AND, d, num[i]);
    }
    return rs;
}

pair<int, int> add_bits(int x, int y, int z = -1) {
    int t = add_operation(OP_XOR, x, y);
    int nxt = add_operation(OP_AND, x, y);
    if (z != -1) {
        nxt = add_operation(OP_AND, x, y);
        nxt = add_operation(OP_OR, nxt, add_operation(OP_AND, t, z));
        t = add_operation(OP_XOR, t, z);
    }
    return make_pair(t, nxt);
}

vector<int> add_numbers(vector<int> a, vector<int> b) {
    int nxt = -1;
    vector<int> rs(a.size());
    for (int i = 0; i < (int)a.size(); i += 1) {
        auto [x, new_nxt] = add_bits(a[i], b[i], nxt);
        nxt = new_nxt;
        rs[i] = x;
    }
    return rs;
}

vector<int> get_or(vector<int> a, vector<int> b) {
    vector<int> rs(a.size());
    for (int i = 0; i < (int)a.size(); i += 1) {
        rs[i] = add_operation(OP_OR, a[i], b[i]);
    }
    return rs;
}

vector<int> get_zero(int sz) {
    vector<int> rs(sz);
    for (int i = 0; i < sz; i += 1) {
        rs[i] = add_operation(OP_ZERO, 0, 0);
    }
    return rs;
}

int condition_get(int c, int a, int b) {
    int x = add_operation(OP_GREATER, a, c);
    int y = add_operation(OP_AND, b, c);
    int z = add_operation(OP_XOR, x, y);
    return z;
}

vector<int> condition_get(int c, vector<int> a, vector<int> b) {
    int sz = a.size();
    vector<int> rs(sz);
    for (int i = 0; i < sz; i += 1) {
        rs[i] = condition_get(c, a[i], b[i]);
    }
    return rs;
}

int compare(vector<int> a, vector<int> b, int sz) {
    int rs = add_operation(OP_ZERO, 0, 0);
    for (int i = 0; i < sz; i += 1) {
        int cond = add_operation(OP_XOR, a[i], b[i]);
        int new_rs = condition_get(cond, rs, b[i]);
        rs = new_rs;
    }
    return rs;
}

pair<int, int> condition_swap(int c, int a, int b) {
    int new_a = condition_get(c, a, b);
    int x = add_operation(OP_XOR, a, b);
    int new_b = add_operation(OP_XOR, new_a, x);
    return make_pair(new_a, new_b);
}

pair<vector<int>, vector<int>> condition_swap(int c, vector<int> a, vector<int> b) {
    int sz = a.size();
    vector<int> new_a(sz), new_b(sz);
    for (int i = 0; i < sz; i += 1) {
        auto [x, y] = condition_swap(c, a[i], b[i]);
        new_a[i] = x;
        new_b[i] = y;
    }
    return make_pair(new_a, new_b);
}

vector<int> merge(vector<int> a, vector<int> b, vector<vector<int>> &arr, vector<pair<int, pair<int, int>>> &way, int comp_sz) {
    if (a.empty()) {
        return b;
    }
    if (b.empty()) {
        return a;
    }
    if (a.size() == 1 && b.size() == 1) {
        int s = a[0];
        int t = b[0];
        int x = compare(arr[t], arr[s], comp_sz);
        way.push_back(make_pair(x, make_pair(s, t)));
        auto [new_arr_s, new_arr_t] = condition_swap(x, arr[s], arr[t]);
        arr[s] = new_arr_s;
        arr[t] = new_arr_t;
        return {a[0], b[0]};
    }
    vector<int> alo, ahi;
    vector<int> blo, bhi;
    for (int i = 0; i < (int)a.size(); i += 1) {
        if (i % 2 == 0) {
            alo.push_back(a[i]);
        } else {
            ahi.push_back(a[i]);
        }
    }
    for (int i = 0; i < (int)b.size(); i += 1) {
        if (i % 2 == 0) {
            blo.push_back(b[i]);
        } else {
            bhi.push_back(b[i]);
        }
    }
    vector<int> x = merge(alo, blo, arr, way, comp_sz);
    vector<int> y = merge(ahi, bhi, arr, way, comp_sz);
    vector<int> c;
    int i = 0;
    int j = 0;
    while (i < (int)x.size() || j < (int)y.size()) {
        if (i < (int)x.size()) {
            c.push_back(x[i]);
            i += 1;
        }
        if (j < (int)y.size()) {
            c.push_back(y[j]);
            j += 1;
        }
    }
    int nd = c.size();
    if (nd % 2 == 0) {
        // nd -= 1;
    }
    for (int i = 1; i + 1 < nd; i += 2) {
        int s = c[i];
        int t = c[i + 1];
        int x = compare(arr[t], arr[s], comp_sz);
        way.push_back(make_pair(x, make_pair(s, t)));
        auto [new_arr_s, new_arr_t] = condition_swap(x, arr[s], arr[t]);
        arr[s] = new_arr_s;
        arr[t] = new_arr_t;
    }
    return c;
}

void go_back(vector<vector<int>> &arr, vector<pair<int, pair<int, int>>> &way) {
    for (int i = (int)way.size() - 1; i >= 0; i -= 1) {
        auto [x, st] = way[i];
        auto [s, t] = st;
        auto [new_arr_s, new_arr_t] = condition_swap(x, arr[s], arr[t]);
        arr[s] = new_arr_s;
        arr[t] = new_arr_t;
    }
}

void go_forward(vector<vector<int>> &arr, vector<pair<int, pair<int, int>>> &way) {
    for (int i = 0; i < (int)way.size(); i += 1) {
        auto [x, st] = way[i];
        auto [s, t] = st;
        auto [new_arr_s, new_arr_t] = condition_swap(x, arr[s], arr[t]);
        arr[s] = new_arr_s;
        arr[t] = new_arr_t;
    }
}

vector<int> sort(vector<int> x, vector<vector<int>> &arr, vector<pair<int, pair<int, int>>> &way, int comp_sz) {
    if (x.size() <= 1) {
        return x;
    }
    int sz = (int)x.size();
    vector<int> a, b;
    for (int i = 0; i < sz; i += 1) {
        if (i < sz / 2) {
            a.push_back(x[i]);
        } else {
            b.push_back(x[i]);
        }
    }
    a = sort(a, arr, way, comp_sz);
    b = sort(b, arr, way, comp_sz);
    vector<int> srtd = merge(a, b, arr, way, comp_sz);
    return srtd;
}

// 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]) {
    int n = la / (bts + name_bts);
    int m = lb / (name_bts + name_bts);
    int t = 0;
    vector<vector<int>> names;
    for (int i = 0; i < n; i += 1) {
        vector<int> f(name_bts);
        for (int j = 0; j < name_bts; j += 1) {
            f[j] = t + j;
        }
        t += name_bts;
        names.push_back(f);
    }
    vector<vector<int>> numbers;
    for (int i = 0; i < n; i += 1) {
        vector<int> f(bts);
        for (int j = 0; j < bts; j += 1) {
            f[j] = t + j;
        }
        t += bts;
        numbers.push_back(f);
    }
    vector<vector<int>> senders;
    for (int i = 0; i < m; i += 1) {
        vector<int> f(name_bts);
        for (int j = 0; j < name_bts; j += 1) {
            f[j] = t + j;
        }
        t += name_bts;
        senders.push_back(f);
    }
    vector<vector<int>> recipients;
    for (int i = 0; i < m; i += 1) {
        vector<int> f(name_bts);
        for (int j = 0; j < name_bts; j += 1) {
            f[j] = t + j;
        }
        t += name_bts;
        recipients.push_back(f);
    }

    c = t;
    operations.clear();
    operands.clear();

    vector<pair<int, pair<int, int>>> names_way;
    vector<int> names_srtd(n);
    for (int i = 0; i < n; i += 1) {
        names_srtd[i] = i;
    }
    names_srtd = sort(names_srtd, names, names_way, name_bts);
    go_forward(numbers, names_way);

    vector<vector<int>> senders_nums(m);
    if (0) {
        for (int i = 0; i < m; i += 1) {
            vector<int> num = get_zero(bts);
            for (int j = 0; j < n; j += 1) {
                num = get_or(num, get_if_equal(senders[i], names[names_srtd[j]], numbers[names_srtd[j]]));
            }
            senders_nums[i] = num;
        }
    } else {
        int zero = add_operation(OP_ZERO, 0, 0);
        int one = add_operation(OP_ONE, 0, 0);
        vector<vector<int>> a(n + m);
        vector<vector<int>> b(n + m);
        vector<int> x(n), y(m);
        for (int i = 0; i < n; i += 1) {
            x[i] = i;
            a[i] = names[names_srtd[i]];
            a[i].insert(a[i].begin(), zero);
            b[i] = numbers[names_srtd[i]];
        }
        for (int i = 0; i < m; i += 1) {
            y[i] = n + i;
            a[n + i] = senders[i];
            a[n + i].insert(a[n + i].begin(), one);
            b[n + i] = vector<int>(bts, zero);
        }
        vector<pair<int, pair<int, int>>> way;
        vector<int> srtd;
        srtd = merge(x, y, a, way, name_bts + 1);
        go_forward(b, way);
        for (int i = 0; i + 1 < n + m; i += 1) {
            int pos1 = srtd[i];
            int pos2 = srtd[i + 1];
            vector<int> x = a[pos1];
            vector<int> y = a[pos2];
            x.erase(x.begin());
            y.erase(y.begin());
            int e = check_equal(x, y);
            b[pos2] = condition_get(e, b[pos2], b[pos1]);
        }
        go_back(b, way);
        for (int i = 0; i < m; i += 1) {
            senders_nums[i] = b[n + i];
        }
    }
    vector<vector<int>> results(n);
    if (0) {
        for (int i = 0; i < n; i += 1) {
            vector<int> num = get_zero(bts);
            for (int j = 0; j < m; j += 1) {
                auto summand = get_if_equal(names[names_srtd[i]], recipients[j], senders_nums[j]);
                num = add_numbers(num, summand);
            }
            results[names_srtd[i]] = num;
        }
    } else {
        vector<int> rec_sorted(m);
        for (int i = 0; i < m; i += 1) {
            rec_sorted[i] = i;
        }
        vector<pair<int, pair<int, int>>> rec_way;
        rec_sorted = sort(rec_sorted, recipients, rec_way, name_bts);
        go_forward(senders_nums, rec_way);

        int zero = add_operation(OP_ZERO, 0, 0);
        int one = add_operation(OP_ONE, 0, 0);
        vector<vector<int>> a(n + m);
        vector<vector<int>> b(n + m);
        vector<int> x(n), y(m);
        for (int i = 0; i < n; i += 1) {
            x[i] = i;
            a[i] = names[names_srtd[i]];
            a[i].insert(a[i].begin(), one);
            b[i] = vector<int>(bts, zero);
        }
        for (int i = 0; i < m; i += 1) {
            y[i] = n + i;
            a[n + i] = recipients[rec_sorted[i]];
            a[n + i].insert(a[n + i].begin(), zero);
            b[n + i] = senders_nums[rec_sorted[i]];
        }
        vector<pair<int, pair<int, int>>> way;
        vector<int> srtd;
        srtd = merge(x, y, a, way, name_bts + 1);
        go_forward(b, way);
        for (int i = 0; i + 1 < n + m; i += 1) {
            int pos1 = srtd[i];
            int pos2 = srtd[i + 1];
            vector<int> x = a[pos1];
            vector<int> y = a[pos2];
            x.erase(x.begin());
            y.erase(y.begin());
            int e = check_equal(x, y);
            auto summ = add_numbers(b[pos1], b[pos2]);
            b[pos2] = condition_get(e, b[pos2], summ);
        }
        go_back(b, way);
        for (int i = 0; i < n; i += 1) {
            results[names_srtd[i]] = b[i];
        }
    }
    go_back(results, names_way);
    for (int i = 0; i < (int)operations.size(); i += 1) {
        _operations[i + la + lb] = operations[i];
        for (int j = 0; j < 2; j += 1) {
            _operands[i + la + lb][j] = operands[i][j];
        }
    }
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < bts; j += 1) {
            outputs_circuit[i][j] = results[i][j];
        }
    }
    return c;
}

• 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