QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300523#7508. Fast DebuggerdefyersTL 996ms36976kbC++205.2kb2024-01-08 13:41:122024-01-08 13:41:13

Judging History

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

  • [2024-01-08 13:41:13]
  • 评测
  • 测评结果:TL
  • 用时:996ms
  • 内存:36976kb
  • [2024-01-08 13:41:12]
  • 提交

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* (const Func& f, const 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 (const 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* (const Func8& f, const 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(const 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.back();
		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);
	}
	cur->append({END});

	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: 100
Accepted
time: 1ms
memory: 3576kb

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: 0
Accepted
time: 996ms
memory: 36976kb

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 75
0 195 0 245
199 193 6 13
252 73 245 67
0 0 0 0
51 0 0 245
99 26 0 196
51 195 0 75
247 253 247 37
119 198 119 186
235 235 44 36
4 0 181 0
76 228 253 0
51 245 245 33
119 119 176 0
198 198 1 11
199 93 154 3
106 106 152 21
93 92 42 3
236 236 247 147
198 198 204 135
0 51 0 75
119 118 10 151
1...

result:

ok 40000 numbers

Test #3:

score: 0
Accepted
time: 92ms
memory: 36732kb

input:

11978 10000
repeat 3
repeat 3
xor ax dx
xori cx 74
repeat 2
repeat 2
repeat 10
xor bx dx
xori bx 167
xor dx bx
and cx bx
end
xori cx 140
xor bx cx
repeat 5
repeat 2
xor ax cx
xor ax cx
xor bx ax
repeat 2
xor bx cx
xori bx 237
xori ax 68
xor cx cx
and cx bx
xori ax 225
end
xor dx dx
repeat 5
repeat 5...

output:

141 144 167 0
250 230 51 0
243 168 87 0
195 106 164 164
151 138 51 151
94 34 164 94
245 207 174 0
59 152 164 164
219 239 54 147
49 1 27 0
186 96 30 0
70 15 143 0
43 70 0 0
46 207 138 138
150 146 164 50
114 180 164 114
19 155 164 164
69 249 253 147
236 100 5 72
202 160 184 157
192 90 234 0
246 164 78...

result:

ok 40000 numbers

Test #4:

score: -100
Time Limit Exceeded

input:

11981 10000
repeat 5
repeat 4
or cx ax
repeat 2
xor ax ax
repeat 6
xori dx 75
xor cx dx
ori ax 200
xori ax 90
and cx bx
xori bx 10
end
repeat 6
ori dx 63
xor bx dx
end
xor cx cx
xori dx 157
end
xori cx 137
xor bx dx
repeat 5
repeat 3
xori bx 43
xor dx dx
xor cx ax
xori ax 116
xori bx 239
xori dx 87
...

output:

103 34 24 11
0 102 129 2
103 34 24 108
142 108 142 142
253 34 253 201
0 35 253 0
20 111 20 2
71 34 95 0
139 109 139 2
253 34 253 201
35 50 20 209
0 102 133 2
135 49 171 184
0 35 253 2
0 34 205 142
98 239 205 145
2 103 0 2
117 34 13 68
242 235 20 17
165 34 24 210
117 34 192 123
16 160 8 134
18 0 167 ...

result: