Submission #941562

#	Time	Username	Problem	Language	Result	Execution time	Memory
941562		GrindMachine	Alice, Bob, and Circuit (APIO23_abc)	C++17	66 / 100	381 ms	493860 KiB

abc

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) cout << #x << " = " << x << endl;
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#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


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    int ptr = 0;

    // names
    rep(i,n){
        rep(ch,4){
            int x = names[i][ch]-'a';
            rep(bit,5){
                int b = 0;
                if(x&(1<<bit)) b = 1;
                outputs_alice[ptr++] = b;
            }
        }
    }

    // numbers
    rep(i,n){
        rep(bit,16){
            int b = 0;
            if(numbers[i]&(1<<bit)) b = 1;
            outputs_alice[ptr++] = b;
        }
    }

    return ptr;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    int ptr = 0;

    // senders
    rep(i,m){
        rep(ch,4){
            int x = senders[i][ch]-'a';
            rep(bit,5){
                int b = 0;
                if(x&(1<<bit)) b = 1;
                outputs_bob[ptr++] = b;
            }   
        }
    }

    // receivers
    rep(i,m){
        rep(ch,4){
            int x = recipients[i][ch]-'a';
            rep(bit,5){
                int b = 0;
                if(x&(1<<bit)) b = 1;
                outputs_bob[ptr++] = b;
            }   
        }
    }

    return ptr;
}


// 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]
) {
    int n = la/36;
    int m = lb/40;
    int ptr = la+lb;

    auto f = [&](int t, int x, int y){
        operands[ptr][0] = x;
        operands[ptr][1] = y;
        operations[ptr] = t;
        return ptr++;
    };
    
    rep(i,n){
        rep(bit,16){
            outputs_circuit[i][bit] = f(OP_ZERO,0,0);
        }
    }

    rep(j,m){
        vector<int> bits;
        rep(bit,16){
            bits.pb(f(OP_ZERO,0,0));
        }

        int l1 = la+j*20;

        rep(i,n){
            // is i the sender?
            // good = 1 if i is the sender
            int l2 = i*20;
            int good = f(OP_ONE,0,0);
            
            rep(bit,20){
                int temp = f(OP_EQUAL,l1+bit,l2+bit);
                good = f(OP_AND,good,temp);
            }

            l2 = n*20+i*16;

            rep(bit,16){
                int temp = f(OP_AND,l2+bit,good);
                bits[bit] = f(OP_OR,bits[bit],temp); 
            }
        }

        // bits[16] now has the bits of the num to be added
        l1 = la+m*20+j*20;

        rep(i,n){
            // is i the receiver?
            int l2 = i*20;
            int good = f(OP_ONE,0,0);
            
            rep(bit,20){
                int temp = f(OP_EQUAL,l1+bit,l2+bit);
                good = f(OP_AND,good,temp);
            }

            vector<int> add_bits;
            rep(bit,16){
                add_bits.pb(f(OP_AND,bits[bit],good));
            }

            // add add_bits to outputs_circuit[i]
            int carry = f(OP_ZERO,0,0);
            rep(bit,16){
                int x = add_bits[bit], y = outputs_circuit[i][bit];
                int xo_temp = f(OP_XOR,carry,x);
                outputs_circuit[i][bit] = f(OP_XOR,xo_temp,y);
                int temp1 = f(OP_AND,carry,x);
                int temp2 = f(OP_AND,carry,y);
                int temp3 = f(OP_AND,x,y);
                int or_temp = f(OP_OR,temp1,temp2);
                carry = f(OP_OR,or_temp,temp3);
            }
        }
    }

    return ptr;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 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