Submission #749392

#	Time	Username	Problem	Language	Result	Execution time	Memory
749392		BalintR	Alice, Bob, and Circuit (APIO23_abc)	C++17	54 / 100	87 ms	7656 KiB

abc

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

typedef unsigned short ushort;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}

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 K = 16;

void writeNum(bool *out, int &sz, int x){
    FR(j, K) out[sz++] = (x >> j) & 1;
}

int alice(const int n, const char names[][5],  const ushort arr[], bool out[]){
    vector<string> sorted;
    FR(i, n) sorted.pb(string(names[i]));
    sort(ALL(sorted));
    //dbgArr(sorted, SZ(sorted));

    vi permArr(n);

    FR(i, n){
        int p = lbv(sorted, (string(names[i])));
        out[i*n + p] = 1;
        permArr[p] = arr[i];
    }

    int sz = n*n;
    FR(i, n) writeNum(out, sz, permArr[i]);
    return sz;
}

int bob(const int m, const char lrr[][5], const char rrr[][5], bool out[]){
    vector<string> sorted;
    FR(i, m) sorted.pb(string(lrr[i]));
    FR(i, m) sorted.pb(string(rrr[i]));
    UNIQUE(sorted);

    int n = SZ(sorted);
    FR(i, m){
        int a = lbv(sorted, (string(lrr[i])));
        int b = lbv(sorted, (string(rrr[i])));
        out[n*a + b] = 1;
    }

    return n*n;
}

typedef array<int, K> Num;

int sz;
int *ops, (*opIn)[2];

int doOp(int a, int b, int op){
    ops[sz] = op;
    opIn[sz][0] = a;
    opIn[sz][1] = b;
    return sz++;
}

Num add(Num n1, Num n2){
    Num res{};
    int carry[K];

    res[0] = doOp(n1[0], n2[0], OP_XOR);
    carry[0] = doOp(n1[0], n2[0], OP_AND);

    FOR(i, 1, K){
        int a = n1[i];
        int b = n2[i];
        int c = carry[i-1];

        int x = doOp(a, b, OP_XOR);
        res[i] = doOp(x, c, OP_XOR);
        int c1 = doOp(a, b, OP_AND);
        int c2 = doOp(x, c, OP_AND);
        carry[i] = doOp(c1, c2, OP_OR);
    }

    return res;
}

Num andNum(Num a, int x){
    Num res{};
    FR(i, K) res[i] = doOp(a[i], x, OP_AND);
    return res;
}

Num orNum(Num a, Num b){
    Num res{};
    FR(i, K) res[i] = doOp(a[i], b[i], OP_OR);
    return res;
}

int circuit(const int la, const int lb, int OPS[], int OP_IN[][2], int RES[][16]){
    ops = OPS, opIn = OP_IN;
    int n = sqrt(lb);
    sz = la+lb;

    vector<Num> arr(n), vrr(n);
    FR(i, n) FR(j, K) arr[i][j] = n*n + i*K + j;
    FR(i, n) FR(j, K) vrr[i][j] = doOp(0, 0, 0);

    FR(i, n) FR(j, n) vrr[j] = add(vrr[j], andNum(arr[i], la + i*n + j));

    vector<Num> res(n);
    FR(i, n) FR(j, K) res[i][j] = doOp(0, 0, 0);

    FR(i, n) FR(j, n) res[i] = orNum(res[i], andNum(vrr[j], i*n + j));

    FR(i, n) FR(j, K) RES[i][j] = res[i][j];

    //dbgArr(ops, sz);

    return sz;
}

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