QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#64421#4426. Divided Mechanismabdelrahman001#AC ✓45ms3416kbC++202.7kb2022-11-24 19:52:432022-11-24 19:52:45

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-24 19:52:45]
  • Judged
  • Verdict: AC
  • Time: 45ms
  • Memory: 3416kb
  • [2022-11-24 19:52:43]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const int N = 30 + 5, mod = 1e9 + 7;
const int offset = 10;
int n, m, q;
char a[N][N];
char b[N][N];
map<char, int> idx;
string s;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool checkMove(int dir) {
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            if(a[i][j] == 'B') {
                int ni = i + dx[dir];
                int nj = j + dy[dir];
                if(a[ni][nj] == 'A' || ni < 0 || ni >= N || nj < 0 || nj >= N)
                    return false;
            }
        }
    }
    return true;
}

void move(int dir) {
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            if(a[i][j] != 'B')
                b[i][j] = a[i][j];
            else
                b[i][j] = '.';
        }
    }
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            if(a[i][j] != 'B')
                continue;
            int ni = i + dx[dir];
            int nj = j + dy[dir];
            b[ni][nj] = 'B';
        }
    }
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++)
            a[i][j] = b[i][j];
    }
}

bool isSplit() {
    for(int i = offset;i < n + offset;i++) {
        for(int j = offset;j < m + offset;j++) {
            if(a[i][j] == 'B')
                return false;
        }
    }
    return true;
}
void print() {
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            cout << a[i][j];
        }
        cout << '\n';
    }
    cout << endl << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    idx['N'] = 0;
    idx['S'] = 1;
    idx['E'] = 2;
    idx['W'] = 3;
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> m >> q;
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                a[i][j] = '.';
            }
        }
        for(int i = offset;i < n + offset;i++) {
            for(int j = offset;j < m + offset;j++) {
                cin >> a[i][j];
            }
        }

        cin >> s;
        bool yes = false;
        for(auto i : s) {
            while(checkMove(idx[i]))
                move(idx[i]);
            if(isSplit()) {
                yes = true;
                break;
            }
        }
        yes ? cout << "TAK\n" : cout << "NIE\n";
    }

    return 0;
}
/*
3
5 5 3
BBAA.
.BBAA
A.BBA
A..BA
AAAAA
WNW
5 5 7
BBAA.
.BBAA
A.BBA
A..BA
AAAAA
WNWNSEN
7 5 3
.....
.AAA.
.A.A.
.AB..
.A.A.
.AAA.
.....
SNE
*/

詳細信息

Test #1:

score: 100
Accepted
time: 45ms
memory: 3416kb

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