Submission #1190456

#TimeUsernameProblemLanguageResultExecution timeMemory
1190456steveonalex앨리스, 밥, 서킷 (APIO23_abc)C++20
66 / 100
3380 ms2162688 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...