QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723919 | #4426. Divided Mechanism | maspy | AC ✓ | 32ms | 3608kb | C++23 | 8.3kb | 2024-11-08 03:36:42 | 2024-11-08 03:36:43 |
Judging History
answer
#line 2 "/home/maspy/library/my_template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ll8 = __int128;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template <class T> using vvvvvc = vector<vvvvc<T>>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
IN(name)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i))
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i))
#define FORIN(x, A) for (auto&& x : A)
#define FOR_nCk(s, n, k) \
for (ll s = (1 << k) - 1, tmp_var = 0; s < (1 << n); \
tmp_var = s | (s - 1), s = (tmp_var + 1) | (((~tmp_var & -~tmp_var) - 1) >> (__builtin_ctz(s) + 1)))
#define FOR_SUB(t, s) for(ll t = s; t >= 0; t = (t==0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
using ull = unsigned long long;
using uint = unsigned int;
int popcnt(uint x) {
return __builtin_popcount(x);
}
int popcnt(int x) {
return __builtin_popcount(x);
}
int popcnt(ull x) {
return __builtin_popcountll(x);
}
int popcnt(ll x) {
return __builtin_popcountll(x);
}
int bsr(uint x) {
return 31 - __builtin_clz(x);
}
int bsr(ull x) {
return 63 - __builtin_clzll(x);
}
int ctz(int x) {
return __builtin_ctz(x);
}
int ctz(ll x) {
return __builtin_ctzll(x);
}
int ctz(ull x) {
return __builtin_ctzll(x);
}
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template <class T> T ceil(T x, T y) {
assert(y >= 1);
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T> T floor(T x, T y) {
assert(y >= 1);
return (x > 0 ? x / y : (x - y + 1) / y);
}
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
long double __VA_ARGS__; \
IN(__VA_ARGS__)
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
scan(head);
IN(tail...);
}
ll isqrt(ll n) {
ll x = n, y = (n + 1) / 2;
while (y < x) { tie(x, y) = mp(y, (y + n / y) / 2); }
return x;
}
vi s_to_vi(string S, char first_char='a'){
vi A(S.size());
FOR(i, S.size()){
A[i] = S[i] - first_char;
}
return A;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& A) {
os << A.fi << " " << A.se;
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& A) {
for (size_t i = 0; i < A.size(); i++) {
if(i) os << " ";
os << A[i];
}
return os;
}
void print() {
cout << "\n";
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
cout << head;
if (sizeof...(Tail)) cout << " ";
print(forward<Tail>(tail)...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename T>
vector<T> cumsum(vector<T> A) {
ll N = A.size();
vector<T> B(N + 1);
B[0] = T(0);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
return B;
}
vi bin_count(vi& A, ll size) {
vi C(size);
for (auto&& x : A) {
++C[x];
}
return C;
}
template <typename T>
vi argsort(vector<T>& A){
vi ids(A.size());
iota(all(ids), 0);
sort(all(ids), [&](ll i, ll j){
return A[i] < A[j] || (A[i] == A[j] && i < j);
});
return ids;
}
ll binary_search(function<bool(ll)> check, ll ok, ll ng) {
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
if (check(x))
ok = x;
else
ng = x;
}
return ok;
}
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
template <typename T>
vc<T> merge_sort(vc<T>& A, vc<T>& B) {
vc<T> C;
C.reserve(A.size() + B.size());
merge(all(A), all(B), back_inserter(C));
return C;
}
#line 2 "main.cpp"
void solve() {
LL(H, W, Q);
vc<string> G(3 * H);
FOR(x, 3 * H) G[x].assign(3 * W, '.');
FOR3(x, H, H + H) {
STR(T);
FOR(j, W) G[x][W + j] = T[j];
}
H = 3 * H, W = 3 * W;
auto isin = [&](ll x, ll y) -> bool {
return (0 <= x && x < H && 0 <= y && y < W);
};
auto PRINT = [&]() -> void {
FOR(x, H) print(G[x]);
print();
};
auto step = [&](char c) -> bool {
ll dx = 0, dy = 0;
if (c == 'N') { dx = -1, dy = 0; }
elif (c == 'S') { dx = 1, dy = 0; }
elif (c == 'W') { dx = 0, dy = -1; }
elif (c == 'E') { dx = 0, dy = 1; }
while (1) {
FOR(x, H) FOR(y, W) if (G[x][y] == 'B') {
ll nx = x + dx, ny = y + dy;
if (!isin(nx, ny)) { return true; }
if (G[nx][ny] == 'A') return false;
}
// 動かす
if (c == 'N') {
FOR(x, H - 1) FOR(y, W) if (G[x + 1][y] == 'B') {
G[x][y] = 'B', G[x + 1][y] = '.';
}
}
if (c == 'S') {
FOR_R(x, H - 1) FOR(y, W) if (G[x][y] == 'B') {
G[x][y] = '.', G[x + 1][y] = 'B';
}
}
if (c == 'W') {
FOR(x, H) FOR(y, W - 1) if (G[x][y + 1] == 'B') {
G[x][y] = 'B', G[x][y + 1] = '.';
}
}
if (c == 'E') {
FOR(x, H) FOR_R(y, W - 1) if (G[x][y] == 'B') {
G[x][y] = '.', G[x][y + 1] = 'B';
}
}
// PRINT();
}
};
STR(query);
FORIN(c, query) {
// PRINT();
if (step(c)) return print("TAK");
}
print("NIE");
}
signed main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(15);
LL(T);
FOR(_, T) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 32ms
memory: 3608kb
input:
1000 10 9 4 AA...AAAA A......AA A..BBB..A A...B...A A...B...A AA..BBAAA A..BB...A A......AA A...AAAAA AAAAAAAAA WSEN 9 10 4 AAAAAAAAAA A...A....A A......... A..B...B.. AA.BBBBB.. AA..B..B.A AA..A....A AAA.A...AA AAAAAAAAAA ESNE 9 10 7 AAAAAAAAAA A...A....A A......... A..B...B.. AA.BBBBB.. AA..B..B.A...
output:
TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK ...
result:
ok 1000 lines
Extra Test:
score: 0
Extra Test Passed