Submission #750238

#	Time	Username	Problem	Language	Result	Execution time	Memory
750238		bachhoangxuan	Alice, Bob, and Circuit (APIO23_abc)	C++17	54 / 100	84 ms	8856 KiB

abc

#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define se second
#define fi first
// 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[]
) {
    vector<pair<string,int>> name;
    for(int i=0;i<n;i++){
        string s;
        for(int t=0;t<4;t++) s+=names[i][t];
        name.push_back({s,i});
    }
    sort(name.begin(),name.end());
    int l=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++) outputs_alice[l++]=(numbers[name[i].se]>>j)&1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) outputs_alice[l++]=(j==name[i].se);
    }
    return l;
}


// 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++){
        string s,r;
        for(int t=0;t<4;t++){s+=senders[i][t];r+=recipients[i][t];}
        mp[s]=1;mp[r]=1;
    }
    int n=0;
    for(auto &it:mp) it.se=n++;
    int l=0;
    vector<vector<int>> f(n,vector<int>(n,0));
    for(int i=0;i<m;i++){
        string s,r;
        for(int t=0;t<4;t++){s+=senders[i][t];r+=recipients[i][t];}
        f[mp[r]][mp[s]]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) outputs_bob[l++]=f[i][j];
    }
    outputs_bob[l++]=0;
    return l;
}


// Circuit
struct mask{
    vector<int> p;
    mask(int sz=16){p.assign(sz,0);}
};
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {
    int l=la+lb,s0=la+lb-1,n=sqrt(lb-1);
    auto g = [&](int x,int y,int o){
        operations[l]=o;
        operands[l][0]=x;
        operands[l][1]=y;
        return (l++);
    };
    auto add = [&](mask &px,mask &py){
        mask pa;
        int c=s0;
        for(int j=0;j<16;j++){
            int x=px.p[j],y=py.p[j];
            int a=g(x,y,OP_XOR);
            int b=g(x,y,OP_AND);
            int d=g(c,a,OP_XOR);
            int e=g(c,a,OP_AND);
            int f=g(b,e,OP_OR);
            pa.p[j]=d;c=f;
        }
        return pa;
    };
    vector<mask> res(n),ans(n);
    mask f;
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++) res[i].p[j]=g(s0,s0,OP_AND);
        for(int j=0;j<n;j++){
            int cur=la+i*n+j;
            for(int t=0;t<16;t++) f.p[t]=g(cur,j*16+t,OP_AND);
            res[i]=add(res[i],f);
        }
        //for(int j=0;j<16;j++) cout << res[i].p[j] << ' ';
        //cout << '\n';
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++) ans[i].p[j]=g(s0,s0,OP_AND);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int cur=n*16+i*n+j;
            for(int t=0;t<16;t++) f.p[t]=g(cur,res[i].p[t],OP_AND);
            ans[j]=add(ans[j],f);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++) outputs_circuit[i][j]=ans[i].p[j];
    }
    return l;
}

• 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