Submission #932320

#	Time	Username	Problem	Language	Result	Execution time	Memory
932320		minhnhatnoe	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	814 ms	549012 KiB

abc

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

const int NAME_SIZE = 19, NUM_SIZE = 16;

namespace rutils
{
    long long ensure_div(long long a, long long b)
    {
        assert(a % b == 0);
        return a / b;
    }
}

namespace alice_bob_helpers
{
    namespace string_encode
    {
        const int length_offset[5] = {0, 0, 26,
                                      26 + 26 * 26,
                                      26 + 26 * 26 + 26 * 26 * 26};
        int ctoi(const char *a)
        {
            int ptr = 0, result = 0;
            for (; a[ptr]; ptr++)
                result = result * 26 + a[ptr] - 'a';
            return result + length_offset[ptr];
        }
    }
    namespace permutation_encode
    {
        void sort_bits(vector<int> &a, vector<bool> &ops)
        {
            if (a.size() == 1)
                return;

            int pcnt = (a.size() + 1) / 2;

            // Step 1
            {
                vector<bool> vis(pcnt), pops(pcnt);
                // Start with padding's pair
                for (int i = pcnt - 1; i >= 0; i--)
                {
                    for (int ptr = i; !vis[ptr];)
                    {
                        vis[ptr] = true;
                        int csecond = ptr + pcnt != a.size() ? a[ptr + pcnt] : a.size(), nfirst;
                        if (csecond < pcnt)
                            nfirst = csecond + pcnt;
                        else
                            nfirst = csecond - pcnt;

                        int nfpos = find(a.begin(), a.end(), nfirst) - a.begin();
                        if (nfpos >= pcnt)
                        {
                            pops[nfpos - pcnt] = 1; // Cannot be padding's pair
                            swap(a[nfpos - pcnt], a[nfpos]);
                            ptr = nfpos - pcnt;
                        }
                        else
                            ptr = nfpos;
                    }
                }
                ops.insert(ops.end(), pops.begin(), pops.end());
            }

            // Step 2
            {
                vector<int> left(pcnt);
                for (int i = 0; i < left.size(); i++)
                    left[i] = a[i] % pcnt;
                sort_bits(left, ops);
                sort(a.begin(), a.begin() + left.size(), [&](int a, int b)
                     { return a % pcnt < b % pcnt; });

                vector<int> right(a.size() - pcnt);
                for (int i = 0; i < right.size(); i++)
                    right[i] = a[i + pcnt] % pcnt;
                sort_bits(right, ops);
                sort(a.begin() + left.size(), a.end(), [&](int a, int b)
                     { return a % pcnt < b % pcnt; });
            }

            // Step 3
            {
                vector<bool> pops(pcnt, 0);
                for (int i = 0; i < pcnt; i++)
                {
                    if (i + pcnt != a.size() && a[i] > a[i + pcnt])
                    {
                        swap(a[i], a[i + pcnt]);
                        pops[i] = 1;
                    }
                }
                ops.insert(ops.end(), pops.begin(), pops.end());
            }
            assert(is_sorted(a.begin(), a.end()));
        }

        template <typename T>
        vector<bool> sorted_to_permutation(vector<T> a)
        {
            if (a.size() == 0) return {};

            vector<pair<T, int>> x(a.size());
            for (int i=0; i<a.size(); i++) x[i] = {a[i], i};
            sort(x.begin(), x.end());

            vector<int> p(x.size());
            for (int i=0; i<x.size(); i++) p[i] = x[i].second;

            vector<bool> result;
            sort_bits(p, result);

            assert(result.size() <= a.size() * 12);
            result.resize(a.size() * 12);

            return result;
        }
    }
}

namespace circuit_helpers
{
    namespace numbers
    {
        enum BIT_OP
        {
            OP_ZERO,        // f(OP_ZERO,    x0, x1) = 0
            OP_NOR,         // f(OP_NOR,     x0, x1) = !(x0 || x1)
            OP_GREATER,     // f(OP_GREATER, x0, x1) = (x0 > x1)
            OP_NOT_X1,      // f(OP_NOT_X1,  x0, x1) = !x1
            OP_LESS,        // f(OP_LESS,    x0, x1) = (x0 < x1)
            OP_NOT_X0,      // f(OP_NOT_X0,  x0, x1) = !x0
            OP_XOR,         // f(OP_XOR,     x0, x1) = (x0 ^ x1)
            OP_NAND,        // f(OP_NAND,    x0, x1) = !(x0 && x1)
            OP_AND,         // f(OP_AND,     x0, x1) = (x0 && x1)
            OP_EQUAL,       // f(OP_EQUAL,   x0, x1) = (x0 == x1)
            OP_X0,          // f(OP_X0,      x0, x1) = x0
            OP_GEQ,         // f(OP_GEQ,     x0, x1) = (x0 >= x1)
            OP_X1,          // f(OP_X1,      x0, x1) = x1
            OP_LEQ,         // f(OP_LEQ,     x0, x1) = (x0 <= x1)
            OP_OR,          // f(OP_OR,      x0, x1) = (x0 || x1)
            OP_ONE,         // f(OP_ONE,     x0, x1) = 1
            NOT_CONSTRUCTED // Input bits
        };
        struct bit
        {
            int v;
            bit() = delete;
            bit(int v) : v(v) {}
        };

        namespace io
        {
            int input_size = -1, input_ptr = 0;

            vector<pair<BIT_OP, pair<bit, bit>>> cstr;
            bit make_bit(BIT_OP op, bit x, bit y)
            {
                cstr.push_back({op, {x, y}});
                return cstr.size() - 1;
            }

            bit zero = -1, one = -1;
            void init(int isize)
            {
                input_size = isize;
                cstr.assign(isize, pair<BIT_OP, pair<bit, bit>>{NOT_CONSTRUCTED, {-1, -1}});
                zero = make_bit(OP_ZERO, 0, 0);
                one = make_bit(OP_ONE, 0, 0);
            }

            int write(int operation[], int operand[][2], int output[][NUM_SIZE], const vector<vector<bit>> &result)
            {
                assert(input_ptr == input_size);
                for (int i = input_size; i < cstr.size(); i++)
                {
                    operation[i] = cstr[i].first;
                    operand[i][0] = cstr[i].second.first.v;
                    operand[i][1] = cstr[i].second.second.v;
                }

                for (int i = 0; i < result.size(); i++)
                {
                    assert(result[i].size() == NUM_SIZE);
                    for (int j = 0; j < NUM_SIZE; j++)
                        output[i][j] = result[i][j].v;
                }
                return cstr.size();
            }
        }

#define DEF_BIT_OP(op, name) \
    bit operator op(const bit &a, const bit &b) { return io::make_bit(name, a, b); }
        DEF_BIT_OP(^, OP_XOR)
        DEF_BIT_OP(&, OP_AND)
        DEF_BIT_OP(|, OP_OR)
        DEF_BIT_OP(==, OP_EQUAL)
        DEF_BIT_OP(<, OP_LESS)
        DEF_BIT_OP(>, OP_GREATER)
#undef DEF_BIT_OP

        bit blend(bit a, bit b, bit c)
        {
            return (a > c) | (b & c);
        }
        vector<bit> blend(vector<bit> a, vector<bit> b, bit c)
        {
            assert(a.size() == b.size());
            for (int i = 0; i < a.size(); i++)
                a[i] = blend(a[i], b[i], c);
            return a;
        }

        pair<bit, bit> swap_if(bit a, bit b, bit c)
        {
            c = c & (a ^ b);
            return {a ^ c, b ^ c};
        }
        pair<vector<bit>, vector<bit>> swap_if(vector<bit> a, vector<bit> b, bit c)
        {
            assert(a.size() == b.size());
            for (int i = 0; i < a.size(); i++)
                tie(a[i], b[i]) = swap_if(a[i], b[i], c);
            return {a, b};
        }

        bit operator<(vector<bit> lhs, vector<bit> rhs)
        {
            assert(lhs.size() == rhs.size());
            bit result(io::zero);
            for (int i = 0; i < lhs.size(); i++)
                result = blend(lhs[i] < rhs[i], result, lhs[i] == rhs[i]);
            return result;
        }

        vector<bit> operator&(vector<bit> a, bit b)
        {
            for (bit &x : a)
                x = x & b;
            return a;
        }

        vector<bit> operator+(vector<bit> l, vector<bit> r)
        {
            assert(l.size() == r.size());
            vector<bit> result(l.size(), io::zero);
            int ptr = 0;

            for (bit three = io::zero; ptr < l.size(); ptr++)
            {
                bit one = l[ptr], two = r[ptr];
                assert(one.v != -1 && two.v != -1);

                bit four = one ^ two;
                bit five = result[ptr] = four ^ three;
                bit six = one & two;
                bit seven = four & three;
                three = six | seven;
            }

            return result;
        }
    }
    namespace merge_sorted
    {
        template <int SIZE>
        vector<numbers::bit> name_bit_extract(const vector<numbers::bit> &a)
        {
            assert(a.size() == SIZE);
            vector<numbers::bit> result = {a.back()};
            for (int i = 0; i < NAME_SIZE; i++)
                result.push_back(a[i]);
            return result;
        };

        struct operation
        {
            int x, y;
            numbers::bit s;
        };

        template <int SIZE>
        void merge_name_bit(vector<vector<numbers::bit>> &a, vector<int> cset, vector<operation> &ops)
        {
            auto edge = [&](int x, int y)
            {
                x = cset[x], y = cset[y];
                numbers::bit s = name_bit_extract<SIZE>(a[y]) < name_bit_extract<SIZE>(a[x]);
                tie(a[x], a[y]) = numbers::swap_if(a[x], a[y], s);
                ops.push_back({x, y, s});
            };

            assert(cset.size() % 2 == 0);
            if (cset.size() == 2)
            {
                edge(0, 1);
                return;
            }

            vector<int> sset[2];
            for (int i = 0; i < cset.size(); i += 2)
            {
                sset[0].push_back(cset[i]);
                sset[1].push_back(cset[i + 1]);
            }

            merge_name_bit<SIZE>(a, sset[0], ops);
            merge_name_bit<SIZE>(a, sset[1], ops);

            for (int i = 2; i < cset.size(); i++)
                edge(i - 1, i);
        }

        template <int SIZE>
        vector<operation> merge_name_bit(vector<vector<numbers::bit>> &a)
        {
            vector<int> cset(a.size());
            iota(cset.begin(), cset.end(), 0);

            vector<operation> ops;
            merge_name_bit<SIZE>(a, cset, ops);

            return ops;
        }
        void undo_merge(vector<vector<numbers::bit>> &a, vector<operation> &ops)
        {
            while (ops.size())
            {
                operation cop = ops.back();
                ops.pop_back();
                tie(a[cop.x], a[cop.y]) = swap_if(a[cop.x], a[cop.y], cop.s);
            }
        }
    }
    namespace permutation_decode
    {
        void apply_permutation(vector<vector<numbers::bit>> &a, int l, int r, vector<numbers::bit>::iterator &opsit)
        {
            if (r - l + 1 == 1)
                return;
            int pcnt = (r - l + 1 + 1) / 2;

            // Step 1
            for (int i = 0; i < pcnt; i++){
                vector<numbers::bit> &x = a[l + i], &y = l + i + pcnt <= r ? a[l + i + pcnt] : a[l + i];
                tie(x, y) = numbers::swap_if(x, y, *(opsit++));
            }

            // Step 2
            apply_permutation(a, l, l + pcnt - 1, opsit);
            apply_permutation(a, l + pcnt, r, opsit);

            // Step 3
            for (int i = 0; i < pcnt; i++){
                vector<numbers::bit> &x = a[l + i], &y = l + i + pcnt <= r ? a[l + i + pcnt] : a[l + i];
                tie(x, y) = numbers::swap_if(x, y, *(opsit++));
            }
        }
    }
}

// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[])
{
    vector<int> name(n);
    for (int i = 0; i < n; i++)
        name[i] = alice_bob_helpers::string_encode::ctoi(names[i]);

    vector<unsigned short> nums(n);
    copy(numbers, numbers + n, nums.begin());

    vector<pair<int, unsigned short>> a(n);
    for (int i = 0; i < a.size(); i++)
        a[i] = {name[i], nums[i]};
    sort(a.begin(), a.end());

    vector<bool> xandn;
    for (pair<int, unsigned short> &v : a)
    {
        for (int i = 0; i < NAME_SIZE; i++)
            xandn.push_back(v.first & (1 << i));
        for (int i = 0; i < NUM_SIZE; i++)
            xandn.push_back(v.second & (1 << i));
    }

    vector<bool> p_xtoa = alice_bob_helpers::permutation_encode::sorted_to_permutation(name);

    return copy(p_xtoa.begin(), p_xtoa.end(), copy(xandn.begin(), xandn.end(), outputs_alice)) - outputs_alice;
}

// 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<int, int>> msg(m);
    for (int i = 0; i < m; i++)
        msg[i] = {alice_bob_helpers::string_encode::ctoi(senders[i]),
                  alice_bob_helpers::string_encode::ctoi(recipients[i])};
    sort(msg.begin(), msg.end());

    vector<bool> xandy;
    for (pair<int, int> &v : msg)
    {
        for (int i = 0; i < NAME_SIZE; i++)
            xandy.push_back(v.first & (1 << i));
        for (int i = 0; i < NAME_SIZE; i++)
            xandy.push_back(v.second & (1 << i));
    }

    sort(msg.begin(), msg.end(), [](const pair<int, int> &a, const pair<int, int> &b)
         { return a.second < b.second; });
    
    vector<bool> p_xtoy = alice_bob_helpers::permutation_encode::sorted_to_permutation(msg);
    return copy(p_xtoy.begin(), p_xtoy.end(), copy(xandy.begin(), xandy.end(), outputs_bob)) - outputs_bob;
}

// 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])
{
    using namespace circuit_helpers;

    // Step 0: Input
    int n, m;
    vector<vector<numbers::bit>> a, b;
    vector<numbers::bit> p_xtoa, p_xtoy;
    {
        namespace io = numbers::io;
        io::init(la + lb);

        // Step 0.1: Input from Alice
        n = rutils::ensure_div(la, NAME_SIZE + NUM_SIZE + 12);
        a.resize(n);
        for (int i = 0; i < n; i++)
        {
            for (; a[i].size() < NAME_SIZE; a[i].push_back(io::input_ptr++))
                ;
            for (; a[i].size() < NAME_SIZE + NUM_SIZE; a[i].push_back(io::input_ptr++))
                ;
            for (; a[i].size() < NAME_SIZE + NAME_SIZE; a[i].push_back(io::zero))
                ;
            a[i].push_back(io::zero);
        }
        for (int i = 0; i < n * 12; i++)
            p_xtoa.push_back(io::input_ptr++);

        // Step 0.2: Input from Bob
        m = rutils::ensure_div(lb, NAME_SIZE + NAME_SIZE + 12);
        b.resize(m);
        for (int i = 0; i < m; i++)
        {
            for (; b[i].size() < NAME_SIZE; b[i].push_back(io::input_ptr++))
                ;
            for (; b[i].size() < NAME_SIZE + NAME_SIZE; b[i].push_back(io::input_ptr++))
                ;
            b[i].push_back(io::one);
        }
        for (int i = 0; i < m * 12; i++)
            p_xtoy.push_back(io::input_ptr++);

        assert(io::input_ptr == io::input_size);
    }

    // Step 1: Merge sorted arrays of <X, N, 0> and <X, Y, 1> by <1, 3>
    int absize;
    vector<vector<numbers::bit>> c;
    vector<merge_sorted::operation> merge_ops;
    {
        for (absize = 1; absize < a.size() || absize < b.size(); absize <<= 1)
            ;
        for (; a.size() < absize; a.emplace_back(NAME_SIZE + NAME_SIZE + 1, numbers::io::one))
            ;
        for (; b.size() < absize; b.emplace_back(NAME_SIZE + NAME_SIZE + 1, numbers::io::one))
            ;

        c.resize(absize * 2);
        copy(b.begin(), b.end(), copy(a.begin(), a.end(), c.begin()));

        merge_ops = merge_sorted::merge_name_bit<NAME_SIZE + NAME_SIZE + 1>(c);
    }

    // Step 2: Forward pass.
    // <X, N, 0> -> <X, 0, 0>.
    // <X, Y, 1> -> <Y, N, 1>
    {
        vector<numbers::bit> v(NUM_SIZE, numbers::io::zero);
        for (int i = 0; i < n + m; i++)
        {
            vector<numbers::bit> f(c[i].begin(), c[i].begin() + NAME_SIZE),
                s(c[i].begin() + NAME_SIZE, c[i].begin() + NAME_SIZE * 2);
            numbers::bit t = c[i].back();

            vector<numbers::bit> nf = numbers::blend(f, s, t);
            vector<numbers::bit> ns = numbers::blend(vector<numbers::bit>(NUM_SIZE, numbers::io::zero), v, t);
            v = numbers::blend({s.begin(), s.begin() + NUM_SIZE}, v, t);

            vector<numbers::bit> result = nf;
            result.insert(result.end(), ns.begin(), ns.end());
            result.push_back(t);
            c[i] = result;
        }
        for (int i = n + m; i < c.size(); i++)
            c[i] = vector<numbers::bit>(NAME_SIZE + NUM_SIZE + 1, numbers::io::one);
    }

    // Step 3: Undo step 1
    {
        merge_sorted::undo_merge(c, merge_ops);

        a.resize(n);
        copy(c.begin(), c.begin() + n, a.begin());

        b.resize(m);
        copy(c.begin() + absize, c.begin() + absize + m, b.begin());
    }

    // Step 4: Permute b to sort by Y
    {
        vector<numbers::bit>::iterator it = p_xtoy.begin();
        if (b.size())
            circuit_helpers::permutation_decode::apply_permutation(b, 0, b.size() - 1, it);
    }


    // Step 5: Merge sorted arrays of <X, 0, 0> and <Y, N, 1> by <1, 3>
    {
        for (; a.size() < absize; a.emplace_back(NAME_SIZE + NUM_SIZE + 1, numbers::io::one))
            ;
        for (; b.size() < absize; b.emplace_back(NAME_SIZE + NUM_SIZE + 1, numbers::io::one))
            ;

        c.resize(absize * 2);
        copy(b.begin(), b.end(), copy(a.begin(), a.end(), c.begin()));

        merge_ops = merge_sorted::merge_name_bit<NAME_SIZE + NUM_SIZE + 1>(c);
    }

    // Step 6: Backward pass.
    {
        vector<numbers::bit> v(NUM_SIZE, numbers::io::zero);
        for (int i = c.size() - 1; i >= n + m; i--)
            c[i] = vector<numbers::bit>(NUM_SIZE, numbers::io::one);

        for (int i = n + m - 1; i >= 0; i--)
        {
            vector<numbers::bit> x(c[i].begin() + NAME_SIZE, c[i].begin() + NAME_SIZE + NUM_SIZE);
            numbers::bit t = c[i].back();
            v = c[i] = x + v;
            v = blend(vector<numbers::bit>(NUM_SIZE, numbers::io::zero), v, t);
        }
    }

    // Step 7: Undo step 5
    {
        merge_sorted::undo_merge(c, merge_ops);
        a.resize(n);
        copy(c.begin(), c.begin() + n, a.begin());
    }

    // Step 8: Permute a to sort by A
    {
        vector<numbers::bit>::iterator it = p_xtoa.begin();
        permutation_decode::apply_permutation(a, 0, a.size() - 1, it);
    }
    return numbers::io::write(operations, operands, outputs_circuit, a);
}

Compilation message (stderr)

abc.cpp: In function 'void alice_bob_helpers::permutation_encode::sort_bits(std::vector<int>&, std::vector<bool>&)':
abc.cpp:49:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                         int csecond = ptr + pcnt != a.size() ? a[ptr + pcnt] : a.size(), nfirst;
      |                                       ~~~~~~~~~~~^~~~~~~~~~~
abc.cpp:72:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for (int i = 0; i < left.size(); i++)
      |                                 ~~^~~~~~~~~~~~~
abc.cpp:79:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 for (int i = 0; i < right.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~
abc.cpp:91:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                     if (i + pcnt != a.size() && a[i] > a[i + pcnt])
      |                         ~~~~~~~~~^~~~~~~~~~~
abc.cpp: In function 'int circuit_helpers::numbers::io::write(int*, int (*)[2], int (*)[16], const std::vector<std::vector<circuit_helpers::numbers::bit> >&)':
abc.cpp:179:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<circuit_helpers::numbers::BIT_OP, std::pair<circuit_helpers::numbers::bit, circuit_helpers::numbers::bit> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |                 for (int i = input_size; i < cstr.size(); i++)
      |                                          ~~^~~~~~~~~~~~~
abc.cpp:186:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |                 for (int i = 0; i < result.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~
abc.cpp: In function 'std::vector<circuit_helpers::numbers::bit> circuit_helpers::numbers::blend(std::vector<circuit_helpers::numbers::bit>, std::vector<circuit_helpers::numbers::bit>, circuit_helpers::numbers::bit)':
abc.cpp:213:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<circuit_helpers::numbers::bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |             for (int i = 0; i < a.size(); i++)
      |                             ~~^~~~~~~~~~
abc.cpp: In function 'std::pair<std::vector<circuit_helpers::numbers::bit>, std::vector<circuit_helpers::numbers::bit> > circuit_helpers::numbers::swap_if(std::vector<circuit_helpers::numbers::bit>, std::vector<circuit_helpers::numbers::bit>, circuit_helpers::numbers::bit)':
abc.cpp:226:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<circuit_helpers::numbers::bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |             for (int i = 0; i < a.size(); i++)
      |                             ~~^~~~~~~~~~
abc.cpp: In function 'circuit_helpers::numbers::bit circuit_helpers::numbers::operator<(std::vector<circuit_helpers::numbers::bit>, std::vector<circuit_helpers::numbers::bit>)':
abc.cpp:235:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<circuit_helpers::numbers::bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |             for (int i = 0; i < lhs.size(); i++)
      |                             ~~^~~~~~~~~~~~
abc.cpp: In function 'std::vector<circuit_helpers::numbers::bit> circuit_helpers::numbers::operator+(std::vector<circuit_helpers::numbers::bit>, std::vector<circuit_helpers::numbers::bit>)':
abc.cpp:253:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<circuit_helpers::numbers::bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |             for (bit three = io::zero; ptr < l.size(); ptr++)
      |                                        ~~~~^~~~~~~~~~
abc.cpp:259:21: warning: variable 'five' set but not used [-Wunused-but-set-variable]
  259 |                 bit five = result[ptr] = four ^ three;
      |                     ^~~~
abc.cpp: In function 'int alice(int, const char (*)[5], const short unsigned int*, bool*)':
abc.cpp:382:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, short unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  382 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'int circuit(int, int, int*, int (*)[2], int (*)[16])':
abc.cpp:487:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  487 |         for (absize = 1; absize < a.size() || absize < b.size(); absize <<= 1)
      |                          ~~~~~~~^~~~~~~~~~
abc.cpp:487:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  487 |         for (absize = 1; absize < a.size() || absize < b.size(); absize <<= 1)
      |                                               ~~~~~~~^~~~~~~~~~
abc.cpp:489:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  489 |         for (; a.size() < absize; a.emplace_back(NAME_SIZE + NAME_SIZE + 1, numbers::io::one))
      |                ~~~~~~~~~^~~~~~~~
abc.cpp:491:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  491 |         for (; b.size() < absize; b.emplace_back(NAME_SIZE + NAME_SIZE + 1, numbers::io::one))
      |                ~~~~~~~~~^~~~~~~~
abc.cpp:520:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  520 |         for (int i = n + m; i < c.size(); i++)
      |                             ~~^~~~~~~~~~
abc.cpp:545:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  545 |         for (; a.size() < absize; a.emplace_back(NAME_SIZE + NUM_SIZE + 1, numbers::io::one))
      |                ~~~~~~~~~^~~~~~~~
abc.cpp:547:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<circuit_helpers::numbers::bit> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  547 |         for (; b.size() < absize; b.emplace_back(NAME_SIZE + NUM_SIZE + 1, numbers::io::one))
      |                ~~~~~~~~~^~~~~~~~
abc.cpp: In instantiation of 'std::vector<bool> alice_bob_helpers::permutation_encode::sorted_to_permutation(std::vector<_Tp>) [with T = int]':
abc.cpp:395:92:   required from here
abc.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (int i=0; i<a.size(); i++) x[i] = {a[i], i};
      |                           ~^~~~~~~~~
abc.cpp:112:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (int i=0; i<x.size(); i++) p[i] = x[i].second;
      |                           ~^~~~~~~~~
abc.cpp: In instantiation of 'std::vector<bool> alice_bob_helpers::permutation_encode::sorted_to_permutation(std::vector<_Tp>) [with T = std::pair<int, int>]':
abc.cpp:426:91:   required from here
abc.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (int i=0; i<a.size(); i++) x[i] = {a[i], i};
      |                           ~^~~~~~~~~
abc.cpp:112:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int>, std::allocator<std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (int i=0; i<x.size(); i++) p[i] = x[i].second;
      |                           ~^~~~~~~~~
abc.cpp: In instantiation of 'void circuit_helpers::merge_sorted::merge_name_bit(std::vector<std::vector<circuit_helpers::numbers::bit> >&, std::vector<int>, std::vector<circuit_helpers::merge_sorted::operation>&) [with int SIZE = 39]':
abc.cpp:325:33:   required from 'std::vector<circuit_helpers::merge_sorted::operation> circuit_helpers::merge_sorted::merge_name_bit(std::vector<std::vector<circuit_helpers::numbers::bit> >&) [with int SIZE = 39]'
abc.cpp:497:78:   required from here
abc.cpp:305:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |             for (int i = 0; i < cset.size(); i += 2)
      |                             ~~^~~~~~~~~~~~~
abc.cpp:314:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  314 |             for (int i = 2; i < cset.size(); i++)
      |                             ~~^~~~~~~~~~~~~
abc.cpp: In instantiation of 'void circuit_helpers::merge_sorted::merge_name_bit(std::vector<std::vector<circuit_helpers::numbers::bit> >&, std::vector<int>, std::vector<circuit_helpers::merge_sorted::operation>&) [with int SIZE = 36]':
abc.cpp:325:33:   required from 'std::vector<circuit_helpers::merge_sorted::operation> circuit_helpers::merge_sorted::merge_name_bit(std::vector<std::vector<circuit_helpers::numbers::bit> >&) [with int SIZE = 36]'
abc.cpp:553:77:   required from here
abc.cpp:305:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |             for (int i = 0; i < cset.size(); i += 2)
      |                             ~~^~~~~~~~~~~~~
abc.cpp:314:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  314 |             for (int i = 2; i < cset.size(); i++)
      |                             ~~^~~~~~~~~~~~~

• 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