oj.uz

Submission #941562

# Submission time Handle Problem Language Result Execution time Memory
941562 2024-03-09T07:13:21 Z GrindMachine Alice, Bob, and Circuit (APIO23_abc) C++17
66 / 100
 381 ms 493860 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1224 KB Correct!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1224 KB Correct!
2 Correct 1 ms 1424 KB Correct!

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1224 KB Correct!
2 Correct 1 ms 1424 KB Correct!
3 Correct 108 ms 25556 KB Correct!
4 Correct 108 ms 26592 KB Correct!

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5708 KB Correct!
2 Correct 107 ms 76684 KB Correct!
3 Correct 119 ms 97900 KB Correct!

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5708 KB Correct!
2 Correct 107 ms 76684 KB Correct!
3 Correct 119 ms 97900 KB Correct!
4 Correct 96 ms 78196 KB Correct!
5 Correct 123 ms 97552 KB Correct!

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5708 KB Correct!
2 Correct 107 ms 76684 KB Correct!
3 Correct 119 ms 97900 KB Correct!
4 Correct 96 ms 78196 KB Correct!
5 Correct 123 ms 97552 KB Correct!
6 Correct 86 ms 73196 KB Correct!
7 Correct 172 ms 146816 KB Correct!

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 381 ms 493860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 381 ms 493860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1224 KB Correct!
2 Correct 1 ms 1424 KB Correct!
3 Correct 108 ms 25556 KB Correct!
4 Correct 108 ms 26592 KB Correct!
5 Correct 7 ms 5708 KB Correct!
6 Correct 107 ms 76684 KB Correct!
7 Correct 119 ms 97900 KB Correct!
8 Correct 96 ms 78196 KB Correct!
9 Correct 123 ms 97552 KB Correct!
10 Correct 86 ms 73196 KB Correct!
11 Correct 172 ms 146816 KB Correct!
12 Runtime error 381 ms 493860 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -