QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100786 | #4426. Divided Mechanism | Yanagi_Origami# | AC ✓ | 95ms | 3460kb | C++20 | 2.3kb | 2023-04-28 08:04:44 | 2023-04-28 08:04:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forn(i,a,b) for(int i=(a); (i)<(b); i++)
#define fore(i,a,b) for(int i=(a); (i)<=(b); i++)
#define pb push_back
#define sz(a) static_cast<int>((a).size())
#define F first
#define S second
constexpr int INF = 1'000'000'000;
using ll = long long;
constexpr int C = 4;
unordered_map<char, array<int, 2>> dir = {
{'N', {-1, 0}}, {'S', {1, 0}}, {'E', {0, 1}}, {'W', {0, -1}}
};
bool oob(int n, int m, int x, int y)
{
return min(x,y)<0 || x>=n || y>=m;
}
void solve()
{
int n,m,Q; cin>>n>>m>>Q;
int n2 = C * n, m2 = C * m;
vector<string> s(n2, string(m2, '.'));
vector<string> s1(n2, string(m2, '.'));
forn(i,0,n) forn(j,0,m)
{
cin>>s[i+n+n/2][j+m+m/2];
}
string upd; cin>>upd;
forn(z,0,Q)
{
// cout<<"z="<<z<<endl;
char c = upd[z];
array<int, 2> d = dir[c];
int min_dist=INF;
forn(i,0,n2) forn(j,0,m2)
{
if(s[i][j] != 'B') continue;
int x=i+d[0], y=j+d[1];
while(!oob(n2, m2, x, y))
{
if (s[x][y] != '.') break;
x += d[0];
y += d[1];
}
if (oob(n2, m2, x, y) || s[x][y] == 'B') continue;
min_dist = min(min_dist, abs(x - i) + abs(y - j) - 1);
}
// cout<<"z="<<z<<" min_dist="<<min_dist<<'\n';
if (min_dist == INF)
{
cout<<"TAK\n";
return;
}
// update map
forn(i,0,n2) forn(j,0,m2)
{
// cout<<">>> 1: "<<i<<" "<<j<<endl;
if (s[i][j] != 'B') s1[i][j] = s[i][j];
else s1[i][j] = '.';
}
forn(i,0,n2) forn(j,0,m2)
{
// cout<<">>> 2: "<<i<<" "<<j<<endl;
if (s[i][j] != 'B') continue;
int x = i + min_dist * d[0];
int y = j + min_dist * d[1];
s1[x][y] = 'B';
}
forn(i,0,n2) forn(j,0,m2) s[i][j] = s1[i][j];
// forn(i,0,n2) cout<<s[i]<<'\n';
// cout<<'\n';
}
cout<<"NIE\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t; cin>>t;
forn(i,0,t) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 95ms
memory: 3460kb
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