Submission #1190296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190296		steveonalex	Alice, Bob, and Circuit (APIO23_abc)	C++20	12 / 100	86 ms	10012 KiB

abc

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

#include "abc.h"

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


int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
    for(int i = 0; i < 16; ++i) outputs_alice[i] = GETBIT(numbers[0], i);
    return 16;
}


int bob(const int m,const char senders[][5],const char recipients[][5],bool outputs_bob[]) {
    for(int i = 0; i < 10; ++i) outputs_bob[i] = GETBIT(m, i);
    return 10;
}

struct LogicGate{
    int x, y, type;
    LogicGate(int x = -1, int y = -1, int type = -1): x(x), y(y), type(type){}
};

vector<LogicGate> gay;

vector<int> add_gate(vector<int> x, int y, int off_set = 0){
    for(int it = off_set; it < (int) x.size(); ++it){
        int i = x[it];
        int j = gay.size();
        gay.push_back(LogicGate(i, y, OP_XOR));
        int k = gay.size();
        gay.push_back(LogicGate(i, y, OP_AND));

        x[it] = j;
        y = k;
    }

    return x;
}

vector<int> add_gate(vector<int> x, vector<int> y){
    if (x.size() < y.size()) swap(x, y);
    for(int i = 0; i < (int) y.size(); ++i){
        x = add_gate(x, y[i], i);
    }
    return x;
}

vector<int> multiply_gate(vector<int> x, vector<int> y){
    vector<int> ans;
    for(int i = 0; i < (int) x.size(); ++i){
        ans.push_back(gay.size());
    }
    gay.push_back(LogicGate(0, 0, OP_ZERO));

    for(int i = 0; i < (int) y.size(); ++i)
    for(int j = 0; j < (int) x.size(); ++j){
        if (i + j < (int)x.size()){
            int k = gay.size();
            gay.push_back(LogicGate(y[i], x[j], OP_AND));
            ans = add_gate(ans, k, i + j);
        }
    }
    return ans;
}

int circuit(const int la, const int lb, int operations[],int operands[][2],int outputs_circuit[][16]) {
    for(int i = 0; i < la + lb; ++i) gay.emplace_back();

    vector<int> x(la), y(lb);
    for(int i = 0; i < la; ++i) x[i] = i;
    for(int j = 0; j < lb; ++j) y[j] = j + la;

    vector<int> z = multiply_gate(x, y);
    for(int i = la + lb; i < (int) gay.size(); ++i) {
        operations[i] = gay[i].type;
        operands[i][0] = gay[i].x;
        operands[i][1] = gay[i].y;
    }

    for(int i = 0; i< 16; ++i) outputs_circuit[0][i] = z[i];
    return gay.size();
}

 

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