oj.uz

Submission #874579

# Submission time Handle Problem Language Result Execution time Memory
874579 2023-11-17T10:43:55 Z Stickfish Alice, Bob, and Circuit (APIO23_abc) C++17
66 / 100
 124 ms 65020 KB 
#include "abc.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 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

void write_kbit(bool* arr, int k, int i, int x) {
    for (int t = 0; t < k; ++t) {
        arr[i + t] = x & (1 << t);
    }
}

string to_string(const char s[5]) {
    string ans;
    for (int i = 0; i < 5; ++i) {
        if (s[i] == '\0')
            break;
        ans.push_back(s[i]);
    }
    return ans;
}

// 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<string, int>> nms(n);
    for (int i = 0; i < n; ++i) {
        nms[i] = {to_string(names[i]), i};
    }
    sort(nms.begin(), nms.end());
    for (int i = 0; i < n; ++i) {
        write_kbit(outputs_alice, 16, 16 * i, numbers[nms[i].second]);
    }

    for (int i = 0; i < n; ++i) {
        write_kbit(outputs_alice, 5, 16 * n + 5 * i, nms[i].second);
    }

    return 21 * n;
}


// 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<string, string>> edges(m);
    for (int i = 0; i < m; ++i) {
        edges[i] = {to_string(senders[i]), to_string(recipients[i])};
    }
    vector<string> names;
    for (int i = 0; i < m; ++i) {
        names.push_back(edges[i].first);
        names.push_back(edges[i].second);
    }
    sort(names.begin(), names.end());
    names.resize(unique(names.begin(), names.end()) - names.begin());
    int n = names.size();
    vector<vector<int>> edg(n, vector<int>(n, 0));
    for (auto [s, r] : edges) {
        int si = lower_bound(names.begin(), names.end(), s) - names.begin();
        int ri = lower_bound(names.begin(), names.end(), r) - names.begin();
        ++edg[si][ri];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            write_kbit(outputs_bob, 16, 16 * (i * n + j), edg[i][j]);
        }
    }
    return 16 * n * n;
}

int siz = 0;
int* opt;
int (*opr)[2];

inline void new_op(int a, int b, int op_type) {
    opt[siz] = op_type;
    opr[siz][0] = a;
    opr[siz][1] = b;
    ++siz;
}

int alg_sum(int a, int b, int k) {
    vector<int> digs(k);
    digs[0] = siz;
    new_op(a, b, OP_XOR);
    int conv = siz;
    new_op(a, b, OP_AND);
    for (int i = 1; i < k; ++i) {
        new_op(a + i, b + i, OP_XOR);
        new_op(siz - 1, conv, OP_XOR);
        digs[i] = siz - 1;

        int cache = siz;
        new_op(a + i, b + i, OP_OR); // cache
        new_op(conv, cache, OP_AND); // cache + 1
        new_op(a + i, b + i, OP_AND); // cache + 2

        new_op(cache + 1, cache + 2, OP_OR);
        conv = siz - 1;

        
    }
    int ans = siz;
    for (int i = 0; i < k; ++i)
        new_op(digs[i], digs[i], OP_AND);
    return ans;
}

int alg_multdig(int a, int cond, int k) {
    int ans = siz;
    for (int i = 0; i < k; ++i) {
        new_op(a + i, cond, OP_AND);
    }
    return ans;
}

int alg_multndig(int a, int cond, int k) {
    int ans = siz;
    for (int i = 0; i < k; ++i) {
        new_op(a + i, cond, OP_GREATER);
    }
    return ans;
}

int alg_inv(int a, int k) {
    int ans = siz;
    for (int i = 0; i < k; ++i) {
        new_op(a + i, a + i, OP_NOT_X0);
    }
    int add = siz;
    new_op(0, 0, OP_ONE);
    for (int i = 1; i < k; ++i) {
        new_op(0, 0, OP_ZERO);
    }
    return alg_sum(ans, add, k);
}

int alg_mult(int a, int b, int k) {
    int ans = siz; 
    for (int i = 0; i < k; ++i)
        new_op(0, 0, OP_ZERO);
    for (int i = 0; i < k; ++i) {
        int val = siz;
        for (int j = 0; j < k; ++j) {
            if (j < i)
                new_op(0, 0, OP_ZERO);
            else
                new_op(b + i, a + j - i, OP_AND);
        }
        ans = alg_sum(ans, val, k);

    }
    return ans;
}

int alg_gr(int a, int b, int k) {
    int ans = siz;
    new_op(0, 0, OP_ZERO);
    int alleq = siz;
    new_op(0, 0, OP_ONE);
    for (int i = k - 1; i >= 0; --i) {
        new_op(a + i, b + i, OP_GREATER);
        new_op(siz - 1, alleq, OP_AND);
        new_op(siz - 1, ans, OP_OR);
        ans = siz - 1;

        new_op(a + i, b + i, OP_EQUAL);
        new_op(siz - 1, alleq, OP_AND);
        alleq = siz - 1;
    }
    return ans;
}

pair<int, int> swap_if(int a, int b, int cond, int k) {
    int sm = alg_sum(a, b, k);
    int ac = alg_inv(alg_multdig(a, cond, k), k);
    int anc = alg_inv(alg_multndig(a, cond, k), k);
    int bc = alg_inv(alg_multdig(b, cond, k), k);
    int bnc = alg_inv(alg_multndig(b, cond, k), k);
    // newa = sum - ac - bnc
    // newb = sum - bc - anc
    
    int newa = alg_sum(sm, ac, k);
    newa = alg_sum(newa, bnc, k);
    
    int newb = alg_sum(sm, bc, k);
    newb = alg_sum(newb, anc, k);

    return {newa, newb};
}

// 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]
) {
    opt = operations;
    opr = operands;
    siz = la + lb;
    int n = la / 21;
    for (int i = 0; i < 16; ++i) {
        new_op(0, 0, OP_ZERO);
    }
    vector<int> answers(n);
    for (int i = 0; i < n; ++i) {
        answers[i] = la + lb;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int val = alg_mult(16 * i, la + 16 * (i * n + j), 16);
            answers[j] = alg_sum(val, answers[j], 16);
        }
    }

    vector<int> permut(n);
    for (int i = 0; i < n; ++i) {
        permut[i] = 16 * n + i * 5;
    }
    for (int t = 0; t < n + 5; ++t) {
        vector<int> conds;
        for (int i = t % 2; i + 1 < n; i += 2) {
            conds.push_back(alg_gr(permut[i + 1], permut[i], 5));
        }
        for (int i = t % 2; i + 1 < n; i += 2) {
            auto [pi, pj] = swap_if(permut[i], permut[i + 1], conds[i / 2], 5);
            auto [vi, vj] = swap_if(answers[i], answers[i + 1], conds[i / 2], 16);
            permut[i] = pj;
            permut[i + 1] = pi;
            answers[i] = vj;
            answers[i + 1] = vi;
        }
    }


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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1304 KB Correct!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1304 KB Correct!
2 Correct 2 ms 1228 KB Correct!

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1304 KB Correct!
2 Correct 2 ms 1228 KB Correct!
3 Correct 51 ms 5228 KB Correct!
4 Correct 46 ms 5372 KB Correct!

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 45984 KB Correct!
2 Correct 73 ms 49452 KB Correct!
3 Correct 82 ms 48440 KB Correct!

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 45984 KB Correct!
2 Correct 73 ms 49452 KB Correct!
3 Correct 82 ms 48440 KB Correct!
4 Correct 92 ms 47752 KB Correct!
5 Correct 95 ms 48864 KB Correct!

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 45984 KB Correct!
2 Correct 73 ms 49452 KB Correct!
3 Correct 82 ms 48440 KB Correct!
4 Correct 92 ms 47752 KB Correct!
5 Correct 95 ms 48864 KB Correct!
6 Correct 93 ms 59384 KB Correct!
7 Correct 124 ms 65020 KB Correct!

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 8200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 8200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1304 KB Correct!
2 Correct 2 ms 1228 KB Correct!
3 Correct 51 ms 5228 KB Correct!
4 Correct 46 ms 5372 KB Correct!
5 Correct 48 ms 45984 KB Correct!
6 Correct 73 ms 49452 KB Correct!
7 Correct 82 ms 48440 KB Correct!
8 Correct 92 ms 47752 KB Correct!
9 Correct 95 ms 48864 KB Correct!
10 Correct 93 ms 59384 KB Correct!
11 Correct 124 ms 65020 KB Correct!
12 Runtime error 39 ms 8200 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -