QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#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
*/

Details

Tip: Click on the bar to expand more detailed information

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