QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300509 | #7508. Fast Debugger | defyers | WA | 1ms | 3500kb | C++20 | 5.1kb | 2024-01-08 13:28:17 | 2024-01-08 13:28:17 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define int long long
using ll = long long;
using LL = long long;
using pii = pair<int, int>;
const int AND = 1;
const int OR = 2;
const int XOR = 3;
const int FOR = 4;
const int END = 5;
const int AX = 256;
const int BX = 257;
const int CX = 258;
const int DX = 259;
struct Action{
int op, a, b;
};
string operandToString(int x){
if(x == AX) return "ax";
if(x == BX) return "bx";
if(x == CX) return "cx";
if(x == DX) return "dx";
return to_string(x);
}
ostream& operator<< (ostream& out, const Action& A){
map<int, string> ops = {
{AND, "AND"},
{OR, "OR"},
{XOR, "XOR"},
{FOR, "FOR"},
{END, "END"}
};
out << ops[A.op] << ' ' << operandToString(A.a) << ' ' << operandToString(A.b);
return out;
}
int readInstruction(){
string s; cin >> s;
if(s.substr(0, 3) == "and")
return AND;
else if(s.substr(0, 2) == "or"){
return OR;
}else if(s.substr(0, 3) == "xor"){
return XOR;
}else if(s == "repeat"){
return FOR;
}else if(s == "end"){
return END;
}
assert(false);
return 0;
}
int readOperand(){
string s; cin >> s;
if(isalpha(s[0])){
return 256 + (s[0] - 'a');
}else{
return stoi(s);
}
}
int getValue(int state, int oper){
if(oper >= 256){
return (state >> (oper - 256)) & 1;
}else{
return oper;
}
}
struct Func{
int a[16];
Func() = default;
Func(int op, int a, int b){
for(int msk = 0; msk < 16; msk++){
int x = getValue(msk, a);
int y = getValue(msk, b);
int z;
assert(x <= 1);
assert(y <= 1);
if (op == AND) {
z = x & y;
} else if (op == OR) {
z = x | y;
} else if (op == XOR) {
z = x ^ y;
}
int ap = a - 256;
int new_msk = (msk & (15 - (1 << ap))) | (z << ap);
Func::a[msk] = new_msk;
}
}
static Func Id(){
Func res;
for(int i = 0; i < 16; i++){
res.a[i] = i;
}
return res;
}
};
Func operator* (Func f, Func g){
Func h;
for(int i = 0; i < 16; i++){
h.a[i] = g.a[f.a[i]];
}
return h;
}
template<class T>
T pow (T f, int k) {
return k == 0 ? T::Id() : pow(f * f, k / 2) * (k % 2 ? f : T::Id());
}
struct Func8 : vector<Func> {
Func8 () = default;
static Func8 Id(){
Func8 res;
for(int i = 0; i < 8; i++){
res.push_back(Func::Id());
}
return res;
}
Func8(int op, int a, int b){
// cout << a << ' ' << b << endl;
for(int i = 0; i < 8; i++){
push_back(Func(op, a >= 256 ? a : (a >> i) & 1, b >= 256 ? b : (b >> i) & 1));
}
}
};
Func8 operator* (Func8 f, Func8 g){
Func8 res;
for(int i = 0; i < 8; i++){
res.push_back(f[i] * g[i]);
}
return res;
}
struct node{
vector<Func8> ps; Func8 tot = Func8::Id();
vector<int> cnt; int sz;
vector<node*> ch; node* par = nullptr;
Action act;
node* append(Action act){
if(act.op != END){
node *v = new node();
v->act = act;
ch.push_back(v); v->par = this;
if(act.op == FOR)
return v;
else
return this;
}else{
return par;
}
}
};
void dfs0(node* v){
int sz = 0;
v->ps.push_back(Func8::Id());
v->cnt.push_back(0);
for(auto u : v->ch){
dfs0(u);
v->ps.push_back(v->ps.back() * u->tot);
v->cnt.push_back(v->cnt.back() + u->sz);
}
if(v->act.op == FOR){
v->tot = pow(v->ps.back(), v->act.a);
v->sz = v->cnt.back() * v->act.a;
}else{
v->tot = Func8(v->act.op, v->act.a, v->act.b);
v->sz = 1;
}
v->sz = min(v->sz, 1LL << 30);
}
Func8 dfs(node* v, int k){
assert(k >= 0);
if(k == 0) return Func8::Id();
if(v->act.op != FOR){
assert(k == 1);
return v->tot;
}else{
int psz = v->cnt.size();
Func8 res = pow(v->ps.back(), k / psz);
int pos = --upper_bound(all(v->cnt), k % psz) - v->cnt.begin();
res = res * v->ps[pos];
if(pos < v->ch.size()){
res = res * dfs(v->ch[pos], k % psz - v->cnt[pos]);
}
return res;
}
}
void solve(int TC) {
int n, q; cin >> n >> q;
vector<Action> A;
for(int i = 0; i < n; i++){
int ins = readInstruction();
if(ins == FOR){
int k; cin >> k;
A.push_back({FOR, k});
}else if(ins == END){
A.push_back({END});
}else{
int a = readOperand(), b = readOperand();
A.push_back({ins, a, b});
}
}
node *root = new node();
root->act = {FOR, 1, 0};
node *cur = root;
for(auto act : A){
cur = cur->append(act);
}
dfs0(root);
assert(cur == root);
// for(auto act : A){
// cout << act << '\n';
// }
for(int i = 0; i < q; i++){
int k, a, b, c, d; cin >> k >> a >> b >> c >> d;
int a2 = 0, b2 = 0, c2 = 0, d2 = 0;
Func8 ans = dfs(root, k);
for(int i = 0; i < 8; i++){
int v = ((a >> i) & 1)
+ ((b >> i) & 1) * 2
+ ((c >> i) & 1) * 4
+ ((d >> i) & 1) * 8;
v = ans[i].a[v];
a2 += (v & 1 ? (1 << i) : 0);
b2 += (v & 2 ? (1 << i) : 0);
c2 += (v & 4 ? (1 << i) : 0);
d2 += (v & 8 ? (1 << i) : 0);
}
cout << a2 << ' ' << b2 << ' ' << c2 << ' ' << d2 << '\n';
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3500kb
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 3 3 4 1 3 3
result:
wrong answer 3rd numbers differ - expected: '2', found: '3'