QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189970 | #4426. Divided Mechanism | berarchegas# | AC ✓ | 26ms | 3532kb | C++20 | 4.5kb | 2023-09-28 03:22:14 | 2023-09-28 03:22:14 |
Judging History
answer
#include <bits/stdc++.h>
#include <iostream>
// #define int long long
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v)),v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
// std::mt19937_64 rng64((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(
// (int) std::chrono::steady_clock::now().time_since_epoch().count()
1239010
);
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
b%=m;
ll ans = 1;
for (; e; b = b * b % m, e /= 2)
if (e & 1) ans = ans * b % m;
return ans;
}
// debug:
template<class T>void print_vector(vector<T> &v){
rep(i,0,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];
}
void dbg_out() {cerr << endl; }
template<typename Head, typename ... Tail> void dbg_out(Head H,Tail... T){
cerr << ' ' << H;
dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl
#else
#define dbg(...) 42
#endif
//
const int N = 35;
char mat[N][N];
char aux[N][N];
void solve(){
int n, m , q;
cin >> n >> m >> q;
rep(i,0,N)rep(j,0,N){
mat[i][j] = '.';
}
rep(i,1,n+1){
rep(j,1,m+1){
char ch;
cin >> ch;
mat[i + 10][j + 10] = ch;
}
}
string s;
cin >> s;
for(auto dir : s){
int mn = 1e9;
// find mn
if(dir == 'N'){
rep(j,0,N){
int last = -1e9;
rep(i,0,N){
if(mat[i][j] == 'A')last = i;
else if(mat[i][j] == 'B'){
mn = min(mn,abs(i - last));
}
}
}
}else if(dir == 'S'){
rep(j,0,N){
int last = 1e9;
for(int i=N-1;i>=0;i--){
if(mat[i][j] == 'A')last = i;
else if(mat[i][j] == 'B'){
mn = min(mn,abs(i - last));
}
}
}
}else if(dir == 'W'){
rep(i,0,N){
int last = -1e9;
rep(j,0,N){
if(mat[i][j] == 'A')last = j;
else if(mat[i][j] == 'B'){
mn = min(mn,abs(j - last));
}
}
}
}else{
rep(i,0,N){
int last = 1e9;
for(int j = N-1; j>=0;j--){
if(mat[i][j] == 'A')last = j;
else if(mat[i][j] == 'B'){
mn = min(mn,abs(j - last));
}
}
}
}
mn--;
// dbg(mn);
if(mn > N){
cout << "TAK" << endl;
return;
}
// go:
rep(i,0,N)rep(j,0,N){
if(mat[i][j] == 'B')aux[i][j] = '.';
else aux[i][j] = mat[i][j];
}
rep(i,0,N)rep(j,0,N)if(mat[i][j] == 'B'){
int ii = i,jj = j;
if(dir == 'N')ii-=mn;
else if(dir == 'S')ii+=mn;
else if(dir == 'W')jj-=mn;
else jj+=mn;
aux[ii][jj] = 'B';
}
rep(i,0,N)rep(j,0,N)mat[i][j] = aux[i][j];
}
cout << "NIE" << endl;
}
int32_t main(){
fastio;
int t;
cin >> t;
while(t--){
solve();
}
// math -> gcd it all
// Did you swap N,M? N=1?
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 26ms
memory: 3532kb
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