QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203442#7508. Fast Debuggerucup-team004#WA 44ms20464kbC++205.7kb2023-10-06 17:29:302023-10-06 17:29:31

Judging History

你现在查看的是最新测评结果

  • [2023-10-06 17:29:31]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:20464kb
  • [2023-10-06 17:29:30]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

using TransBit = std::array<int, 16>;
using Trans = std::array<TransBit, 8>;

Trans identity() {
    Trans t;
    for (int i = 0; i < 8; i++) {
        std::iota(t[i].begin(), t[i].end(), 0);
    }
    return t;
}

Trans operator*(const Trans &a, const Trans &b) {
    Trans c;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 16; j++) {
            c[i][j] = b[i][a[i][j]];
        }
    }
    return c;
}

Trans get(std::string o, int x, int y) {
    Trans t;
    for (int i = 0; i < 8; i++) {
        for (int a = 0; a < 16; a++) {
            int vx = a >> x & 1;
            int vy = a >> y & 1;
            int b = a ^ (vx << x);
            int v;
            if (o == "or") {
                v = vx | vy;
            } else if (o == "and") {
                v = vx & vy;
            } else {
                v = vx ^ vy;
            }
            b ^= v << x;
            t[i][a] = b;
        }
    }
    return t;
}

Trans geti(std::string o, int x, int y) {
    Trans t;
    for (int i = 0; i < 8; i++) {
        for (int a = 0; a < 16; a++) {
            int vx = a >> x & 1;
            int vy = y >> i & 1;
            int b = a ^ (vx << x);
            int v;
            if (o == "or") {
                v = vx | vy;
            } else if (o == "and") {
                v = vx & vy;
            } else {
                v = vx ^ vy;
            }
            b ^= v << x;
            t[i][a] = b;
        }
    }
    return t;
}

Trans power(Trans a, int b) {
    Trans res = identity();
    for (; b; b /= 2, a = a * a) {
        if (b % 2) {
            res = res * a;
        }
    }
    return res;
}

std::array<int, 4> trans(std::array<int, 4> a, Trans t) {
    std::array<int, 4> ans{};
    for (int i = 0; i < 8; i++) {
        int mask = 0;
        for (int j = 0; j < 4; j++) {
            mask |= (a[j] >> i & 1) << j;
        }
        mask = t[i][mask];
        for (int j = 0; j < 4; j++) {
            ans[j] |= (mask >> j & 1) << i;
        }
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    constexpr int inf = 1E9 + 1;

    std::vector<int> path{0};
    std::vector<Trans> val{identity()};
    std::vector<int> rep{1};
    std::vector<std::vector<int>> adj(1);
    std::vector<int> cnt{0};

    int tot = 1;
    for (int i = 0; i < n; i++) {
        std::string ins;
        std::cin >> ins;

        if (ins == "repeat") {
            int m;
            std::cin >> m;
            path.push_back(tot++);
            val.push_back(identity());
            rep.push_back(m);
            adj.push_back({});
            cnt.push_back(0);
        } else if (ins == "end") {
            int x = path.back();
            path.pop_back();
            int y = path.back();
            adj[y].push_back(x);
            val[y] = val[y] * power(val[x], rep[x]);
            cnt[y] = std::min(1LL * inf, cnt[y] + 1LL * cnt[x] * rep[x]);
        } else if (ins.back() == 'i') {
            std::string x;
            std::cin >> x;
            int y;
            std::cin >> y;

            int u = path.back();
            int v = tot++;
            val.push_back(geti(ins, x[0] - 'a', y));
            rep.push_back(1);
            adj.push_back({});
            cnt.push_back(1);
            adj[u].push_back(v);
            val[u] = val[u] * val[v];
            cnt[u] = std::min(inf, cnt[u] + 1);
        } else {
            std::string x, y;
            std::cin >> x >> y;

            int u = path.back();
            int v = tot++;
            val.push_back(get(ins, x[0] - 'a', y[0] - 'a'));
            rep.push_back(1);
            adj.push_back({});
            cnt.push_back(1);
            adj[u].push_back(v);
            val[u] = val[u] * val[v];
            cnt[u] = std::min(inf, cnt[u] + 1);
        }
    }

    auto dfs = [&](auto self, int x) -> void {
        std::vector<int> tmp;
        int u = x, i = 0;
        while (i < adj[u].size()) {
            int y = adj[u][i];
            if (cnt[y] < inf) {
                tmp.push_back(y);
                i++;
            } else {
                u = y, i = 0;
            }
        }
        adj[x] = std::move(tmp);
        for (auto y : adj[x]) {
            self(self, y);
        }
    };
    dfs(dfs, 0);

    std::vector<std::vector<int>> prec(tot);
    std::vector<std::vector<Trans>> prev(tot);
    for (int i = 0; i < tot; i++) {
        prec[i].resize(adj[i].size() + 1);
        prev[i].resize(adj[i].size() + 1);
        prev[i][0] = identity();
        for (int j = 0; j < adj[i].size(); j++) {
            int x = adj[i][j];
            prec[i][j + 1] = std::min(1LL * inf, prec[i][j] + 1LL * rep[x] * cnt[x]);
            prev[i][j + 1] = prev[i][j] * power(val[x], rep[x]);
        }
    }
    
    for (int i = 0; i < q; i++) {
        int k;
        std::cin >> k;
        std::array<int, 4> v;
        for (int j = 0; j < 4; j++) {
            std::cin >> v[j];
        }

        int x = 0;
        while (k > 0) {
            int j = std::upper_bound(prec[x].begin(), prec[x].end(), k) - prec[x].begin() - 1;
            k -= prec[x][j];
            v = trans(v, prev[x][j]);
            if (k == 0) {
                break;
            }
            x = adj[x][j];
            assert(rep[x] != -1);
            v = trans(v, power(val[x], k / cnt[x]));
            k %= cnt[x];
        }

        for (int j = 0; j < 4; j++) {
            std::cout << v[j] << " \n"[j == 3];
        }
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

6 2
repeat 5
xor ax bx
xori ax 3
and cx ax
xor cx dx
end
10 1 2 4 3
8 4 1 2 3

output:

0 2 2 3
4 1 3 3

result:

ok 8 numbers

Test #2:

score: -100
Wrong Answer
time: 44ms
memory: 20464kb

input:

11982 10000
repeat 2
repeat 2
andi bx 201
xori cx 241
repeat 4
xor cx bx
xor ax dx
repeat 8
or dx bx
xori dx 22
end
repeat 2
xor dx bx
xor dx bx
repeat 7
xor bx bx
or cx dx
and bx cx
end
andi dx 33
xori ax 179
xori bx 56
end
xori dx 63
xori cx 91
xori dx 228
or cx dx
repeat 6
xor cx dx
xori bx 198
x...

output:

24 195 0 251
0 195 0 84
51 133 242 208
220 73 85 99
0 0 0 0
51 0 0 84
99 123 0 140
51 195 0 122
215 160 215 92
199 114 131 211
26 26 73 240
5 0 0 0
204 228 73 0
51 85 85 33
114 114 37 213
22 22 65 2
51 237 222 42
51 51 161 49
237 236 110 42
145 213 215 147
118 118 17 115
0 51 0 122
131 130 35 10
239...

result:

wrong answer 4th numbers differ - expected: '75', found: '251'