제출 #931920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931920		becaido	앨리스, 밥, 서킷 (APIO23_abc)	C++17	100 / 100	558 ms	370044 KiB

abc

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "abc.h"
using namespace std;

#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back

const int OP_ZERO    = 0;
const int OP_NOR     = 1;
const int OP_GREATER = 2;
const int OP_NOT_X1  = 3;
const int OP_LESS    = 4;
const int OP_NOT_X0  = 5;
const int OP_XOR     = 6;
const int OP_NAND    = 7;
const int OP_AND     = 8;
const int OP_EQUAL   = 9;
const int OP_X0      = 10;
const int OP_GEQ     = 11;
const int OP_X1      = 12;
const int OP_LEQ     = 13;
const int OP_OR      = 14;
const int OP_ONE     = 15;

const int DS_LEN = 55;
const int X_LEN = 19;
const int Y_LEN = 19;
const int W_LEN = 16;

struct ds {
    int x, y, w, t;
    ds() {}
    ds(int x, int y, int w, int t) : x(x), y(y), w(w), t(t) {}
} a[2400];

string perm_str(vector<int> id) {
    int n = id.size();
    if (n == 0) return "";
    vector<int> p(n), val, tag(n);
    vector<vector<pair<int, int>>> st(n);
    string res;
    val = id;
    auto rec = [&](auto rec, int l, int r)->void {
        if (l == r) return;
        int mid = (l + r) / 2, len = mid - l + 1;
        fill(tag.begin() + l, tag.begin() + mid + 1, 0);
        FOR (i, l, r) p[val[i]] = i;
        auto check = [&](int i) {
            tag[i] = 1;
            while (true) {
                int x = val[i];
                int y = (x < len ? x + len : x - len);
                if (y > r) break;
                if (p[y] <= mid) {
                    if (tag[p[y]] != 0) break;
                    tag[p[y]] = 2;
                    i = p[y] + len;
                } else {
                    if (tag[p[y] - len] != 0) break;
                    tag[p[y] - len] = 1;
                    i = p[y] - len;
                }
            }
        };
        check(mid);
        FOR (i, l, mid) if (i + len <= r) {
            if (tag[i] == 0) check(i);
            if (tag[i] == 1) res += "0";
            else {
                res += "1";
                swap(id[i], id[i + len]);
                swap(val[i], val[i + len]);
            }
        }
        FOR (i, l, r) if (val[i] >= len) {
            val[i] -= len;
            st[id[i]].pb(l, r);
        }
        rec(rec, l, mid);
        rec(rec, mid + 1, r);
        FOR (i, l, r) if (st[id[i]].size() && st[id[i]].back() == make_pair(l, r)) {
            val[i] += len;
            st[id[i]].pop_back();
        }
        FOR (i, l, mid) if (i + len <= r) {
            if (val[i] < val[i + len]) res += "0";
            else {
                res += "1";
                swap(id[i], id[i + len]);
                swap(val[i], val[i + len]);
            }
        }
    };
    rec(rec, 0, n - 1);
    return res;
}
string perm_str(vector<int> lid, vector<int> rid) {
    int n = lid.size();
    vector<int> id(n), inv(n);
    FOR (i, 0, n - 1) inv[rid[i]] = i;
    FOR (i, 0, n - 1) id[i] = inv[lid[i]];
    return perm_str(id);
}

int conv(const char s[]) {
    int val = 0, n = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        n++;
        val = 26 * val + s[i] - 'a';
    }
    if (n == 1) return 1 + val;
    if (n == 2) return 1 + 26 + val;
    if (n == 3) return 1 + 26 + 26 * 26 + val;
    if (n == 4) return 1 + 26 + 26 * 26 + 26 * 26 * 26 + val;
}

int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int l, int r) {
        return conv(names[l]) < conv(names[r]);
    });
    int la = 0;
    auto gen = [&](int x, int len) {
        FOR (i, 0, len - 1) outputs_alice[la++] = (x >> i & 1);
    };
    FOR (i, 0, n - 1) {
        gen(conv(names[id[i]]), X_LEN);
        gen(conv(names[id[i]]), Y_LEN);
        gen(numbers[id[i]]    , W_LEN);
        gen(0                 , 1    );
    }
    string res = perm_str(id);
    for (char c : res) gen(c - '0', 1);
    return la;
}

int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]) {
    vector<int> xid(m), yid(m);
    iota(xid.begin(), xid.end(), 0);
    iota(yid.begin(), yid.end(), 0);
    sort(xid.begin(), xid.end(), [&](int l, int r) {
        return conv(senders[l]) < conv(senders[r]);
    });
    sort(yid.begin(), yid.end(), [&](int l, int r) {
        return conv(recipients[l]) < conv(recipients[r]);
    });
    int lb = 0;
    auto gen = [&](int x, int len) {
        FOR (i, 0, len - 1) outputs_bob[lb++] = (x >> i & 1);
    };
    FOR (i, 0, m - 1) {
        gen(conv(senders[xid[i]])   , X_LEN);
        gen(conv(recipients[xid[i]]), Y_LEN);
        gen(0                       , W_LEN);
        gen(1                       , 1    );
    }
    string res = perm_str(xid, yid);
    for (char c : res) gen(c - '0', 1);
    return lb;
}

int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]) {
    auto get_n = [&](int len) {
        auto cal = [&](int n) {
            if (n == 0) return 0;
            int sz = DS_LEN * n;
            queue<int> q;
            q.push(n);
            while (q.size()) {
                int x = q.front();
                q.pop();
                if (x == 1) continue;
                sz += x - (x & 1);
                q.push(x >> 1);
                q.push((x + 1) >> 1);
            }
            return sz;
        };
        int l = 0, r = 1000;
        while (l < r) {
            int mid = (l + r) / 2;
            if (cal(mid) >= len) r = mid;
            else l = mid + 1;
        }
        return l;
    };
    int n = get_n(la), m = get_n(lb), lc = la + lb;
    if (n == 0) return 0;
    auto op = [&](int ty, int x, int y) {
        operations[lc] = ty;
        operands[lc][0] = x;
        operands[lc][1] = y;
        return lc++;
    };
    auto opf = [&](int ty, int x, int f, int len) {
        int s = lc;
        FOR (i, 0, len - 1) op(ty, x + i, f);
        return s;
    };
    auto ops = [&](int ty, int x, int y, int len) {
        int s = lc;
        FOR (i, 0, len - 1) op(ty, x + i, y + i);
        return s;
    };
    if (m == 0) {
        FOR (i, 0, n - 1) FOR (j, 0, W_LEN - 1) outputs_circuit[i][j] = op(OP_ZERO, 0, 0);
        return lc;
    }
    FOR (i, 0, n - 1) {
        int pre = DS_LEN * i;
        a[i] = ds(pre, pre + X_LEN, pre + X_LEN + Y_LEN, pre + X_LEN + Y_LEN + W_LEN);
    }
    FOR (i, 0, m - 1) {
        int pre = la + DS_LEN * i;
        a[n + i] = ds(pre, pre + X_LEN, pre + X_LEN + Y_LEN, pre + X_LEN + Y_LEN + W_LEN);
    }
    int sz = 1;
    while (sz < n + m) sz <<= 1;
    vector<int> id(sz, -1), st;
    FOR (i, 0, n - 1) id[i] = i;
    FOR (i, 0, m - 1) id[sz - i - 1] = n + i;
    auto swaps = [&](int &x, int &y, int f, int len) {
        int xf, yf, z, nx, ny;
        xf = opf(OP_GREATER, x , f , len);
        yf = opf(OP_AND    , y , f , len);
        nx = ops(OP_OR     , xf, yf, len);
        z  = ops(OP_XOR    , y , nx, len);
        ny = ops(OP_XOR    , x , z , len);
        x = nx, y = ny;
    };
    auto swap_a = [&](int x, int y, int f) {
        swaps(a[x].x, a[y].x, f, X_LEN);
        swaps(a[x].y, a[y].y, f, Y_LEN);
        swaps(a[x].w, a[y].w, f, W_LEN);
        swaps(a[x].t, a[y].t, f, 1    );
    };
    auto comp = [&](int x, int y, bool isy) {
        int px = (isy == 0 ? a[x].x : a[x].y);
        int py = (isy == 0 ? a[y].x : a[y].y);
        int lsml, lbig;
        for (int i = X_LEN - 1; i >= 0; i--) {
            int sml = op(OP_LESS   , px + i, py + i);
            int big = op(OP_GREATER, px + i, py + i);
            if (i != X_LEN - 1) {
                sml = op(OP_GREATER, sml, lbig);
                big = op(OP_GREATER, big, lsml);
                sml = op(OP_OR     , sml, lsml);
                big = op(OP_OR     , big, lbig);
            }
            lsml = sml, lbig = big;
        }
        if (isy == 0) {
            int big = op(OP_GREATER, a[x].t, a[y].t);
            big  = op(OP_GREATER, big, lsml);
            lbig = op(OP_OR     , big, lbig);
        } else {
            int big = op(OP_LESS, a[x].t, a[y].t);
            big  = op(OP_GREATER, big, lsml);
            lbig = op(OP_OR     , big, lbig);
        }
        st.pb(lbig);
        swap_a(x, y, lbig);
    };
    auto merge = [&](auto merge, int l, int r, bool isy)->void {
        if (l == r) return;
        int mid = (l + r) / 2, len = mid - l + 1;
        FOR (i, l, mid) {
            if (id[i + len] == -1) {
                st.pb(0);
                continue;
            }
            if (id[i] == -1) {
                swap(id[i], id[i + len]);
                st.pb(1);
                continue;
            }
            comp(id[i], id[i + len], isy);
        }
        merge(merge, l, mid, isy);
        merge(merge, mid + 1, r, isy);
    };
    auto undo = [&](auto undo, int l, int r)->void {
        if (l == r) return;
        int mid = (l + r) / 2, len = mid - l + 1;
        undo(undo, mid + 1, r);
        undo(undo, l, mid);
        for (int i = mid; i >= l; i--) {
            if (id[i + len] == -1) {
                if (st.back() == 1) swap(id[i], id[i + len]);
            } else {
                swap_a(id[i], id[i + len], st.back());
            }
            st.pop_back();
        }
    };
    merge(merge, 0, sz - 1, 0);
    int cur = a[id[0]].w;
    FOR (i, 1, n + m - 1) {
         cur        = opf(OP_AND, cur, a[id[i]].t, W_LEN);
         a[id[i]].w = ops(OP_OR , cur, a[id[i]].w, W_LEN);
         cur = a[id[i]].w;
    }
    undo(undo, 0, sz - 1);
    auto perm = [&](auto perm, int l, int r, int &ptr)->void {
        if (l == r) return;
        int mid = (l + r) / 2, len = mid - l + 1;
        FOR (i, l, mid) if (i + len <= r) swap_a(i, i + len, ptr++);
        perm(perm, l, mid, ptr);
        perm(perm, mid + 1, r, ptr);
        FOR (i, l, mid) if (i + len <= r) swap_a(i, i + len, ptr++);
    };
    auto add = [&](int x, int y) {
        array<int, W_LEN> xy, cr;
        cr[1] = op(OP_AND, x, y);
        FOR (i, 1, W_LEN - 1) {
            xy[i] = op(OP_XOR, x + i, y + i);
            if (i < W_LEN - 1) {
                int tmp = op(OP_AND, x + i, y + i);
                cr[i + 1] = op(OP_AND, xy[i], cr[i]    );
                cr[i + 1] = op(OP_OR , tmp  , cr[i + 1]);
            }
        }
        int s = op(OP_XOR, x, y);
        FOR (i, 1, W_LEN - 1) op(OP_XOR, xy[i], cr[i]);
        return s;
    };
    int ptr = la + DS_LEN * m;
    perm(perm, n, n + m - 1, ptr);
    merge(merge, 0, sz - 1, 1);
    cur = opf(OP_ZERO, 0, 0, W_LEN);
    FOR (i, 0, n + m - 1) {
        a[id[i]].w = opf(OP_AND, a[id[i]].w, a[id[i]].t, W_LEN);
        a[id[i]].w = add(cur, a[id[i]].w);
        cur        = opf(OP_AND, a[id[i]].w, a[id[i]].t, W_LEN);
    }
    undo(undo, 0, sz - 1);
    ptr = DS_LEN * n;
    perm(perm, 0, n - 1, ptr);
    FOR (i, 0, n - 1) FOR (j, 0, 15) outputs_circuit[i][j] = a[i].w + j;
    return lc;
}

컴파일 시 표준 에러 (stderr) 메시지

abc.cpp: In function 'int conv(const char*)':
abc.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

• 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: 18 / 18
• Subtask 8: 10 / 10
• Subtask 9: 6 / 6