Submission #927860

#	Time	Username	Problem	Language	Result	Execution time	Memory
927860		hotboy2703	Alice, Bob, and Circuit (APIO23_abc)	C++17	12 / 100	118 ms	10456 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;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair

namespace circum{
    vector <ll> op1;
    vector <pll> op2;
    vector <vector <ll> > out;
    ll la,lb;
    ll ONE,ZERO;
    ll ng(ll x0,ll x1,ll type){
        op1.push_back(type);
        op2.push_back({x0,x1});
        return sz(op1)-1;
    }
    void init(ll A,ll B){
        la = A,lb = B;
        op1.resize(la+lb);
        op2.resize(la+lb);
        ONE = ng(0,0,OP_ONE),ZERO = ng(0,0,OP_ZERO);
    }


    ll cbit(ll x){
        return (x?ONE:ZERO);
    }
    struct num{
        vector <ll> a;
        num(ll x = -1,ll bit = 16){
            if (x!=-1){
                a.resize(bit);
                for (ll i = 0;i < bit;i ++){
                    a[i] = cbit(BIT(x,i));
                }
            }
        }
        num operator + (num y){
            num x = *this;
            if (sz(x.a)<sz(y.a))swap(x,y);
            while (sz(y.a)<sz(x.a))y.a.push_back(ZERO);
            ll mx_sz = max(sz(x.a),sz(y.a));
            num res;
            res.a.resize(mx_sz);
            ll nho = ZERO;
            for (ll i = 0;i < mx_sz;i ++){
                ll nho1 = ng(x.a[i],y.a[i],OP_AND);
                ll a1 = ng(x.a[i],y.a[i],OP_XOR);
                ll nho2 = ng(a1,nho,OP_AND);
                ll a2 = ng(a1,nho,OP_XOR);
                nho = ng(nho1,nho2,OP_OR);
//                if (i <= 2)cout<<x.a[i]<<','<<y.a[i]<<','<<nho1<<','<<a1<<','<<nho2<<','<<a2<<','<<nho<<endl;
                res.a[i] = a2;
            }
//            cout<<endl;
            return res;
        }
        num operator << (ll constant){
            num res;
            res.a.resize(sz(a));
            for (ll i = 0;i < sz(a);i ++){
                if (i>=constant)res.a[i] = a[i-constant];
                else res.a[i] = ZERO;
            }
            return res;
        }
        num operator * (ll id){
            num res;
            for (ll i = 0;i < sz(a);i ++){
                res.a.push_back(ng(a[i],id,OP_AND));
            }
            return res;
        }
    };
    void add_out(num x){
        assert(sz(x.a)==16);
        out.push_back(x.a);
    }
    namespace sub1{
        num val;
        num b;
        void solve(){
            for (ll i = 0;i < 16;i ++){val.a.push_back(i);b.a.push_back(i+16);}
            num ans(0);
            for (ll j = 0;j < 16;j ++){
                ans = ans + (val<<j)*(b.a[j]);
            }
            add_out(ans);
        }
    }
}


// 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==1){
        for (ll i = 0;i < 16;i ++){
            outputs_alice[i] = BIT(numbers[0],i);
        }
        return 16;
    }
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
//    if (n==1){
        for (ll i = 0;i < 16;i ++){
            outputs_bob[i] = BIT(m,i);
        }
        return 16;
//    }
}


// 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 circum;
    init(la,lb);
    if (la+lb==32){
        sub1::solve();
        for (ll i = 0;i < 16;i ++){
            outputs_circuit[0][i] = out[0][i];
        }

        for (ll i = 0;i < sz(op1);i ++){
            operations[i] = op1[i];
            operands[i][0] = op2[i].fi,operands[i][1] = op2[i].se;

        }

    }
    return sz(op1);
}

Compilation message (stderr)

abc.cpp: In function 'int alice(int, const char (*)[5], const short unsigned int*, bool*)':
abc.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^

• 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