Submission #976475

#	Time	Username	Problem	Language	Result	Execution time	Memory
976475		ttamx	Alice, Bob, and Circuit (APIO23_abc)	C++17	54 / 100	100 ms	40676 KiB

abc

#include "abc.h"
#include<bits/stdc++.h>

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


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    map<string,int> mp;
    for(int i=0;i<n;i++)mp[names[i]];
    int idx=0;
    for(auto &[x,y]:mp)y=idx++;
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++){
            outputs_alice[mp[names[i]]*16+j]=(numbers[i]>>j)&1;
        }
    }
    int sz=n*16;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            outputs_alice[sz+i*n+j]=(j==mp[names[i]]);
        }
    }
    return n*16+n*n;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    map<string,int> mp;
    for(int i=0;i<m;i++)mp[senders[i]];
    for(int i=0;i<m;i++)mp[recipients[i]];
    int n=0;
    for(auto &[x,y]:mp)y=n++;
    vector<vector<int>> adj(n,vector<int>(n,0));
    for(int i=0;i<m;i++)adj[mp[recipients[i]]][mp[senders[i]]]++;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<10;k++){
                outputs_bob[(i*n+j)*10+k]=(adj[i][j]>>k)&1;
            }
        }
    }
    return n*n*10;
}


// 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]
) {
    static int n=sqrt(lb/10);
    static int curgate=la+lb;
    static int zerogate=curgate++;
    operations[zerogate]=0;
    operands[zerogate][0]=0;
    operands[zerogate][1]=1;
    static int onegate=curgate++;
    operations[onegate]=15;
    operands[onegate][0]=0;
    operands[onegate][1]=1;
    static auto bitsand=[&](int xgate,int ygate,int &andgate){
        // x&y
        andgate=curgate++;
        operations[andgate]=8;
        operands[andgate][0]=xgate;
        operands[andgate][1]=ygate;
    };
    static auto bitsxor=[&](int xgate,int ygate,int &xorgate){
        // x^y
        xorgate=curgate++;
        operations[xorgate]=6;
        operands[xorgate][0]=xgate;
        operands[xorgate][1]=ygate;
    };
    static auto bitsadd=[&](int xgate,int ygate,int &sumgate,int &carrygate){
        // x+y
        bitsxor(xgate,ygate,sumgate);
        bitsand(xgate,ygate,carrygate);
    };
    struct gateset{
        array<int,16> gates;
        gateset(){
            for(int i=0;i<16;i++)gates[i]=zerogate;
        }
        gateset leftshift(int x){
            gateset res;
            for(int i=0;i+x<16;i++){
                res.gates[i]=gates[i+x];
            }
            return res;
        }
        gateset rightshift(int x){
            gateset res;
            for(int i=x;i<16;i++){
                res.gates[i]=gates[i-x];
            }
            return res;
        }
        gateset gateand(int y){
            gateset res;
            for(int i=0;i<16;i++){
                bitsand(gates[i],y,res.gates[i]);
            }
            return res;
        }
    };
    auto addition=[&](gateset x,gateset y){
        gateset z;
        int carrygate1=zerogate;
        int carrygate2=zerogate;
        int carrygate=zerogate;
        for(int i=0;i<16;i++){
            bitsadd(x.gates[i],y.gates[i],z.gates[i],carrygate1);
            bitsadd(z.gates[i],carrygate,z.gates[i],carrygate2);
            bitsxor(carrygate1,carrygate2,carrygate);
        }
        return z;
    };
    auto multiply=[&](gateset x,gateset y){
        gateset res;
        for(int i=0;i<16;i++){
            res=addition(res,x.gateand(y.gates[i]).rightshift(i));
        }
        return res;
    };
    vector<gateset> a(n),ans(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++){
            a[i].gates[j]=i*16+j;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            gateset b;
            for(int k=0;k<10;k++)b.gates[k]=la+(i*n+j)*10+k;
            ans[i]=addition(ans[i],multiply(a[j],b));
        }
    }
    for(int i=0;i<n;i++){
        gateset res;
        for(int j=0;j<n;j++){
            res=addition(res,ans[j].gateand(16*n+i*n+j));
        }
        for(int j=0;j<16;j++)outputs_circuit[i][j]=res.gates[j];
    }
    return curgate;
}

• 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