Submission #751574

#	Time	Username	Problem	Language	Result	Execution time	Memory
751574		somethingnew	Alice, Bob, and Circuit (APIO23_abc)	C++17	36 / 100	115 ms	35916 KiB

abc

#include "abc.h"
#include "set"
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include "algorithm"
#include "bitset"
#include "cmath"
using namespace std;
const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;
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

void prnt(int &hd, int nm, bool *out) {
    for (int i = 0; i < 16; ++i) {
        out[hd] = (nm >> i) & 1;
        hd++;
    }
}
// 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>> nms(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 5; ++j) {
            nms[i].first += names[i][j];
        }
        nms[i].second = numbers[i];
    }
    sort(nms.begin(), nms.end());
    int hd = 0;
    for (auto i : nms)
        prnt(hd, i.second, outputs_alice);
    return hd;
}


// Bob
int // returns lb
bob(
        /*  in */ const int m,
        /*  in */ const char senders[][5],
        /*  in */ const char recipients[][5],
        /* out */ bool outputs_bob[]
) {
    set<string> names;
    for (int i = 0; i < m; ++i) {
        string stinp, stout;
        for (int j = 0; j < 5; ++j) {
            stinp += senders[i][j];
        }
        names.insert(stinp);
        for (int j = 0; j < 5; ++j) {
            stout += recipients[i][j];
        }
        names.insert(stout);
    }
    vector<string> be;
    for (auto i : names)
        be.push_back(i);
    vector<vector<int>> a(30, vector<int>(30));
    for (int i = 0; i < m; ++i) {
        string stinp, stout;
        for (int j = 0; j < 5; ++j) {
            stinp += senders[i][j];
        }
        for (int j = 0; j < 5; ++j) {
            stout += recipients[i][j];
        }
        int a1 = lower_bound(be.begin(), be.end(), stinp) - be.begin();
        int a2 = lower_bound(be.begin(), be.end(), stout) - be.begin();
        //cout << a1 << ' ' << a2 << '\n';
        a[a1][a2]++;
    }
    int hd = 0;
    for (int i = 0; i < 30; ++i) {
        for (int j = 0; j < 30; ++j) {
            prnt(hd, a[i][j], outputs_bob);
        }
    }
    return hd;
}
int hd, *lst;
int (*op)[2];
int opxor(int a, int b) {
    op[hd][0] = a;
    op[hd][1] = b;
    lst[hd] = OP_XOR;
    return hd++;
}
int opand(int a, int b) {
    op[hd][0] = a;
    op[hd][1] = b;
    lst[hd] = OP_AND;
    return hd++;
}
int opor(int a, int b) {
    op[hd][0] = a;
    op[hd][1] = b;
    lst[hd] = OP_OR;
    return hd++;
}
int opzero() {
    op[hd][0] = 0;
    op[hd][1] = 0;
    lst[hd] = OP_ZERO;
    return hd++;
}
vector<int> pls(vector<int> a, vector<int> b) {
    vector<int> dig;
    int el = opzero();
    for (int i = 0; i < 16; ++i) {
        int vl = opxor(el, opxor(a[i], b[i]));
        dig.push_back(vl);
        int nxel = opor(opand(a[i], b[i]), opor(opand(a[i], el), opand(el, b[i])));
        el = nxel;
    }
    return dig;
}
vector<int> andx(vector<int> a, int x) {
    vector<int> dig;
    for (auto i : a) {
        dig.push_back(opand(i, x));
    }
    return dig;
}
vector<int> mvrgt(vector<int> a, int k) {
    if (k == 0)
        return a;
    int zr = opzero();
    vector<int> dig(16, zr);
    for (int i = 0; i + k < 16; ++i) {
        dig[i + k] = a[i];
    }
    return dig;
}
vector<int> mult(vector<int> a, vector<int> b) {
    vector<int> res = andx(a, b[0]);
    for (int i = 1; i < 16; ++i) {
        res = pls(res, mvrgt(andx(a, b[i]), i));
    }
    return res;
}
vector<int> getnumfromfirst(int x) {
    vector<int> a(16);
    for (int i = 0; i < 16; ++i) {
        a[i] = x + i;
    }
    return a;
}
vector<int> zeronm() {
    vector<int> a(16, opzero());
    return a;
}
// 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 / 16;
    hd = la + lb;
    op = operands;
    lst = operations;
    vector<vector<int>> a(n, zeronm());
    int myind = 0;
    for (int i = 0; i < 30; ++i) {
        for (int j = 0; j < 30; ++j) {
            if (max(i, j) < n)
                a[j] = pls(a[j], mult(getnumfromfirst(i*16), getnumfromfirst(la+myind)));
            myind += 16;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 16; ++j) {
            outputs_circuit[i][j] = a[i][j];
        }
    }
    return hd;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 24 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 6
• Subtask 7: 0 / 18
• Subtask 8: 0 / 10
• Subtask 9: 0 / 6