QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203442 | #7508. Fast Debugger | ucup-team004# | WA | 44ms | 20464kb | C++20 | 5.7kb | 2023-10-06 17:29:30 | 2023-10-06 17:29:31 |
Judging History
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'