QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #203345 | #7104. Halting Problem | siro53 | AC ✓ | 108ms | 4512kb | C++17 | 3.9kb | 2023-10-06 16:51:40 | 2023-10-06 16:51:41 |
Judging History
answer
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
if(a < b) {
a = b;
return 1;
}
return 0;
}
template <class T> inline bool chmin(T &a, T b) {
if(a > b) {
a = b;
return 1;
}
return 0;
}
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << '(' << p.first << ',' << p.second << ')';
return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
os << '{';
for(int i = 0; i < (int)v.size(); i++) {
if(i) { os << ','; }
os << v[i];
}
os << '}';
return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
cerr << " " << x;
debugg(args...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
struct Setup {
Setup() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} __Setup;
using ll = long long;
#define OVERLOAD3(_1, _2, _3, name, ...) name
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define REP1(i, n) for(int i = 0; i < int(n); i++)
#define REP2(i, a, b) for(int i = (a); i < int(b); i++)
#define REP(...) OVERLOAD3(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define REVERSE(v) reverse(ALL(v))
#define SZ(v) ((int)(v).size())
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
constexpr int MOD2 = 998244353;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
void Case(int i) { cout << "Case #" << i << ": "; }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
#pragma endregion Macros
void solve() {
int N;
cin >> N;
vector<tuple<string, int, int>> qs(N);
REP(i, N) {
string s;
cin >> s;
int v, k;
cin >> v;
if(s == "add") {
qs[i] = {s, v, -1};
} else {
cin >> k;
k--;
qs[i] = {s, v, k};
}
}
vector seen(N+1, vector<bool>(256, false));
vector<pair<int, int>> st;
st.emplace_back(0, 0);
seen[0][0] = true;
while(!st.empty()) {
auto [i, r] = st.back();
st.pop_back();
if(i == N) break;
const auto& [s, v, k] = qs[i];
if(s == "add") {
int nr = (r + v) % 256;
if(!seen[i+1][nr]) {
seen[i+1][nr] = true;
st.emplace_back(i+1, nr);
}
} else if(s == "beq") {
int ni = (r == v ? k : i+1);
if(!seen[ni][r]) {
seen[ni][r] = true;
st.emplace_back(ni, r);
}
} else if(s == "bne") {
int ni = (r != v ? k : i+1);
if(!seen[ni][r]) {
seen[ni][r] = true;
st.emplace_back(ni, r);
}
} else if(s == "blt") {
int ni = (r < v ? k : i+1);
if(!seen[ni][r]) {
seen[ni][r] = true;
st.emplace_back(ni, r);
}
} else {
assert(s == "bgt");
int ni = (r > v ? k : i+1);
if(!seen[ni][r]) {
seen[ni][r] = true;
st.emplace_back(ni, r);
}
}
}
REP(r, 256) if(seen[N][r]) {
cout << "Yes\n";
return;
}
cout << "No\n";
}
int main() {
int T{1};
cin >> T;
while(T--) solve();
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
4 2 add 1 blt 5 1 3 add 252 add 1 bgt 252 2 2 add 2 bne 7 1 3 add 1 bne 252 1 beq 252 1
output:
Yes Yes No No
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 108ms
memory: 4512kb
input:
1117 8 bgt 51 8 add 75 add 115 bne 40 3 beq 213 6 bgt 210 4 blt 228 7 bgt 60 2 6 bne 130 3 add 33 bne 74 4 blt 73 6 blt 63 5 bne 138 2 6 beq 131 2 bgt 90 3 add 127 bgt 195 1 blt 244 6 bne 20 3 3 add 53 bne 122 1 blt 251 2 9 add 102 add 161 bne 26 2 blt 5 8 beq 76 3 add 119 bgt 196 3 bne 239 8 blt 15...
output:
No Yes Yes No No Yes Yes No Yes No No No No Yes No No Yes No Yes No No Yes No No No Yes Yes Yes Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes No No No No No Yes No Yes No No No Yes No No No No No Yes No Yes Yes Yes No Yes No Yes No Yes No No No No Yes No No Yes No No Yes No No No Yes Yes Yes Yes No Y...
result:
ok 1117 lines
Extra Test:
score: 0
Extra Test Passed