제출 #1190456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190456		steveonalex	Alice, Bob, and Circuit (APIO23_abc)	C++20	66 / 100	3380 ms	2162688 KiB

abc

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

#include "abc.h"

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


int encode(string s){
    int ans = 0;
    int po = 1;
    for(int i = 1; i < (int) s.size(); ++i){
        ans += po *= 26;
    }
    for(int i = 0; i < (int) s.size(); ++i){
        ans += po * (s[i] - 'a');
        po /= 26;
    }
    return ans;
}

int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
    vector<string> namek;
    for(int i = 0; i < n; ++i){
        namek.emplace_back();
        for(int j =0; j < 5; ++j){
            if (names[i][j] == '\0') break;
            namek.back().push_back(names[i][j]);
        }
    }

    int idx = 0;
    for(int i = 0; i < n; ++i){
        int x = encode(namek[i]);
        for(int j = 0; j < 19; ++j) {
            outputs_alice[idx++] = GETBIT(x, j);
        }
        for(int j = 0; j < 16; ++j) {
            outputs_alice[idx++] = GETBIT(numbers[i], j);
        }
    }

    return idx;
}


int bob(const int m,const char senders[][5],const char recipients[][5],bool outputs_bob[]) {
    vector<string> senders_name;
    for(int i = 0; i < m; ++i){
        senders_name.emplace_back();
        for(int j =0; j < 5; ++j){
            if (senders[i][j] == '\0') break;
            senders_name.back().push_back(senders[i][j]);
        }
    }
    vector<string> recipients_name;
    for(int i = 0; i < m; ++i){
        recipients_name.emplace_back();
        for(int j =0; j < 5; ++j){
            if (recipients[i][j] == '\0') break;
            recipients_name.back().push_back(recipients[i][j]);
        }
    }


    int idx = 0;
    for(int i = 0; i < m; ++i){
        int x = encode(senders_name[i]);
        int y = encode(recipients_name[i]);
        for(int j = 0; j < 19; ++j) {
            outputs_bob[idx++] = GETBIT(x, j);
        }
        for(int j = 0; j < 19; ++j){
            outputs_bob[idx++] = GETBIT(y, j);
        }
    }

    return idx;
}

struct LogicGate{
    int x, y, type;
    LogicGate(int x = -1, int y = -1, int type = -1): x(x), y(y), type(type){}
};

vector<LogicGate> gay;

int create_new_gate(int x, int y, int OP){
    gay.emplace_back(LogicGate(x, y, OP));
    return gay.size() - 1;
}

vector<int> op_add(vector<int> x, int y, int off_set = 0){ // op_add(x[], y, offset) = x + (y << offset)
    for(int it = off_set; it < (int) x.size(); ++it){
        int i = x[it];
        int j = create_new_gate(i, y, OP_XOR);
        int k = create_new_gate(i, y, OP_AND);

        x[it] = j;
        y = k;
    }
    return x;
}

vector<int> op_add(vector<int> x, vector<int> y){  // op_add(x[], y[]) = x[] + y[]
    if (x.size() < y.size()) swap(x, y);
    for(int i = 0; i < (int) y.size(); ++i){
        x = op_add(x, y[i], i);
    }
    return x;
}

vector<int> op_multiply(vector<int> x, vector<int> y){  // op_multiply(x[], y[]) = x[] * y[]
    vector<int> ans;
    for(int i = 0; i < (int) x.size(); ++i){
        ans.push_back(gay.size());
    }
    gay.push_back(LogicGate(0, 0, OP_ZERO));

    for(int i = 0; i < (int) y.size(); ++i)
    for(int j = 0; j < (int) x.size(); ++j){
        if (i + j < (int)x.size()){
            int k = gay.size();
            gay.push_back(LogicGate(y[i], x[j], OP_AND));
            ans = op_add(ans, k, i + j);
        }
    }
    return ans;
}

int op_equal(vector<int> x, vector<int> y){ // op_equal(x[], y[]) -> (x == y)
    if (x.size() != y.size()) assert(false);
    vector<int> z(x.size());
    for(int i = 0; i < (int) x.size(); ++i){
        z[i] = create_new_gate(x[i], y[i], OP_EQUAL);
    }
    int ans = z[0];
    for(int i = 1; i < (int) z.size(); ++i){
        ans = create_new_gate(ans, z[i], OP_AND);
    }
    return ans;
}

vector<int> op_equal_multiply(vector<int> x, vector<int> y, vector<int> z){ // op_equal(x[], y[], z[]) -> (x == y) * z
    if (x.size() != y.size()) assert(false);
    int t = op_equal(x, y);
    vector<int> ans = z;
    for(int &i: ans){
        i = create_new_gate(i, t, OP_AND);
    }
    return ans;
}

int circuit(const int la, const int lb, int operations[],int operands[][2],int outputs_circuit[][16]) {
    int n = la / 35, m = lb / 38;
    gay.reserve(1e7);
    for(int i = 0; i < la + lb; ++i) gay.emplace_back();

    int CACHE_ZERO = create_new_gate(0, 0, OP_ZERO);

    vector<vector<int>> names(n), favorite_number(n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 19; ++j) names[i].push_back(i * 35 + j);
        for(int j = 19; j < 35; ++j) favorite_number[i].push_back(i * 35 + j);
    }

    vector<vector<int>> ans(n);
    for(int i = 0; i < n; ++i){
        ans[i].resize(16, CACHE_ZERO);
    }

    for(int i = 0; i < m; ++i){
        vector<int> u, v;
        for(int j = 0; j < 19; ++j) u.push_back(la + i * 38 + j);
        for(int j = 19; j < 38; ++j) v.push_back(la + i * 38 + j);

        vector<int> sender_favorite_number;
        for(int j = 0; j < n; ++j){
            vector<int> cur = op_equal_multiply(u, names[j], favorite_number[j]);
            if (sender_favorite_number.empty()) sender_favorite_number = cur;
            else{
                sender_favorite_number = op_add(sender_favorite_number, cur);
            }
        }

        for(int j = 0; j < n; ++j){
            vector<int> cur = op_equal_multiply(v, names[j], sender_favorite_number);
            ans[j] = op_add(ans[j], cur);
        }
    }

    for(int i = la + lb; i < (int)gay.size(); ++i){
        operations[i] = gay[i].type;
        operands[i][0] = gay[i].x;
        operands[i][1] = gay[i].y;
    }

    for(int i = 0; i < n; ++i) for(int j = 0; j < 16; ++j){
        outputs_circuit[i][j] = ans[i][j];
    }
    return gay.size();
}

 

• 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