QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325301#5605. A-Mazing Puzzletom0727AC ✓927ms59956kbC++207.3kb2024-02-11 07:33:192024-02-11 07:33:20

Judging History

你现在查看的是最新测评结果

  • [2024-02-11 07:33:20]
  • 评测
  • 测评结果:AC
  • 用时:927ms
  • 内存:59956kb
  • [2024-02-11 07:33:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#if __cplusplus >= 201103L
    struct pairhash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        template<class T, class U>
        size_t operator() (const pair<T,U> &p) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second+ FIXED_RANDOM);
        }
    };
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
    inline int randint(int l, int r) {
        return uniform_int_distribution<int>(l,r)(rng);
    }
    inline double randdouble(double l, double r) {
        return uniform_real_distribution<double>(l,r)(rng);
    }
    inline long long randll(long long l, long long r) {
        mt19937_64 rng2((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
        return uniform_int_distribution<long long>(l, r)(rng2);
    }
#endif
 
#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) 0
#endif

#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define ll long long
#define ull unsigned long long
#define ll128 __int128_t
#define PI 3.14159265358979323846
#define abs(a) ((a>0)?a:-(a))
#define pii pair<int,int>
#define pll pair<ll,ll>

const long double pi = acos(-1.0);
const long double eps = (double)1e-10;

// const int mod = 1e9+7;
int mod;

template<class T>
T qpow(T a, int b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm((int)(x % mod))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return qpow(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = (int)((ll)(x) * rhs.x % mod);
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

const int maxn = 1e6+5;
const int maxm = 1e6+5;


struct State {
    int c1, r1, c2, r2, m, b;
    bool operator<(const State& other) const {
        return tuple {m, b} < tuple {other.m, other.b};
    }
};

pii dp[51][51][51][51];
int c, r, e;  // exit: (e, 0)
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};   // S, W, N, E
bool bad[51][51][4];  // S, W, N, E; if bad, cannot use

char D1, D2;
vector<pii> op;
int mapdir(int d) {
    if (d == 'S') return 0;
    if (d == 'W') return 1;
    if (d == 'N') return 2;
    if (d == 'E') return 3;
}

queue<State> q;
void bfs() {
    while (q.size()) {
        auto [c1, r1, c2, r2, m, b] = q.front(); q.pop();
        // printf("{%d, %d, %d, %d} = %d, %d\n",c1,r1,c2,r2,m,b);

        vector<State> tmp;
        for (int o = 0; o < 4; o++) {
            auto [o1, o2] = op[o];
            int nc1 = c1 + dir[o1][0], nr1 = r1 + dir[o1][1];
            int nc2 = c2 + dir[o2][0], nr2 = r2 + dir[o2][1];
            // if (c1 == 2 && r1 == 0 && c2 == 2 && r2 == 1) {
            //     printf("o1 = %d, o2 = %d, bad1 = %d, bad2 = %d\n",o1,o2,bad[c1][r1][o1],bad[c2][r2][o2]);
            //     printf("nc1 = %d, nr1 = %d, nc2 = %d, nr2 = %d\n",nc1,nr1,nc2,nr2);
            // }
            
            int bp = 0;
            if (bad[c1][r1][o1]) nc1 = c1, nr1 = r1, bp++;
            if (bad[c2][r2][o2]) nc2 = c2, nr2 = r2, bp++;
            if (c1 == e && r1 == 0) nc1 = c1, nr1 = r1;  // 终点:在原地呆着
            if (c2 == e && r2 == 0) nc2 = c2, nr2 = r2;

            State nstate = {nc1, nr1, nc2, nr2, m+1, b+bp};
            tmp.push_back(nstate);
        }
        sort(tmp.begin(), tmp.end());
        for (auto nstate : tmp) {
            auto [C1, R1, C2, R2, M, B] = nstate;
            if (!(C1 == e && R1 == 0) && C1 == C2 && R1 == R2) continue;

            // if (c1 == 4 && r1 == 0 && c2 == 4 && r2 == 1)
            //     printf("{%d, %d, %d, %d} = %d, %d\n",C1,R1,C2,R2,M,B);
            if (pii{M, B} < dp[C1][R1][C2][R2]) {
                dp[C1][R1][C2][R2] = {M, B};
                q.push(nstate);
            }
        }
    }
    cout << dp[e][0][e][0].first << " " << dp[e][0][e][0].second << "\n";
}

int main() {
    int c1, r1, d1, c2, r2, d2;
    cin >> c >> r >> e;
    cin >> c1 >> r1 >> D1 >> c2 >> r2 >> D2;
    memset(dp, 63, sizeof(dp));
    dp[c1][r1][c2][r2] = {0, 0};
    // cout << dp[1][1][1][1].first << " " << dp[1][1][1][1].second << endl;
    d1 = mapdir(D1), d2 = mapdir(D2);
    for (int i = 0; i < 4; i++) {
        op.push_back({d1, d2});
        d1++, d2++;
        d1 %= 4, d2 %= 4;
    }

    int n; cin >> n;
    while (n--) {
        int ci, ri; cin >> ci >> ri;  // (ci, ri) -> (ci, ri+1)
        // (ci, ri): N bad
        // (ci, ri+1): S bad
        bad[ci][ri][2] = 1;
        bad[ci][ri+1][0] = 1;
    }
    cin >> n;
    while (n--) {
        int ci, ri; cin >> ci >> ri;  // (ci, ri) -> (ci+1, ri)
        // (ci, ri): E bad
        // (ci+1, ri): W bad
        bad[ci][ri][3] = 1;
        bad[ci+1][ri][1] = 1;
    }
    for (int i = 1; i <= c; i++) {
        for (int j = 1; j <= r; j++) {
            if (i == 1) bad[i][j][1] = 1;
            if (i == c) bad[i][j][3] = 1;
            if (j == 1) bad[i][j][0] = 1;
            if (j == r) bad[i][j][2] = 1;
        }
    }
    bad[e][1][0] = 0;
    fill(bad[e][0], bad[e][0]+4, 0);

    q.push({c1, r1, c2, r2, 0, 0});
    bfs();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 56552kb

input:

7 4 4
3 2 S 6 3 S
6 1 1 1 2 1 3 2 3 5 1 5 3
11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4

output:

8 1

result:

ok single line: '8 1'

Test #2:

score: 0
Accepted
time: 3ms
memory: 56408kb

input:

3 4 2
1 3 S 3 2 S
1 3 3
5 1 1 2 1 1 2 1 3 2 3

output:

7 2

result:

ok single line: '7 2'

Test #3:

score: 0
Accepted
time: 850ms
memory: 58952kb

input:

50 50 4
15 28 W 9 43 E
49 11 47 42 33 3 4 36 49 21 21 15 34 43 5 32 35 3 21 7 1 40 4 22 44 11 40 46 43 13 26 32 6 44 25 31 46 26 7 45 4 18 10 10 21 3 20 31 8 34 40 42 1 48 43 18 17 9 39 17 2 48 25 39 35 45 43 8 2 22 17 6 46 33 1 38 6 28 25 29 32 45 12 11 20 8 48 14 9 2 24 45 38 1 20 34 5 46 24
50 13...

output:

91 52

result:

ok single line: '91 52'

Test #4:

score: 0
Accepted
time: 531ms
memory: 58976kb

input:

50 50 25
1 50 N 50 50 E
1 45 25
1 16 37

output:

100 26

result:

ok single line: '100 26'

Test #5:

score: 0
Accepted
time: 8ms
memory: 56544kb

input:

10 10 1
10 1 N 10 2 N
0
81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2...

output:

120 4

result:

ok single line: '120 4'

Test #6:

score: 0
Accepted
time: 0ms
memory: 56676kb

input:

3 3 1
3 1 N 3 2 N
0
4 1 2 1 3 2 1 2 2

output:

13 4

result:

ok single line: '13 4'

Test #7:

score: 0
Accepted
time: 0ms
memory: 56480kb

input:

4 3 1
4 1 N 4 2 N
0
6 1 2 1 3 2 1 2 2 3 2 3 3

output:

15 4

result:

ok single line: '15 4'

Test #8:

score: 0
Accepted
time: 5ms
memory: 56432kb

input:

5 5 1
2 4 N 2 1 S
2 2 2 2 4
3 1 1 1 3 3 3

output:

9 4

result:

ok single line: '9 4'

Test #9:

score: 0
Accepted
time: 3ms
memory: 56476kb

input:

5 6 5
4 1 E 5 2 S
3 4 1 3 1 2 1
3 4 2 4 3 4 4

output:

11 2

result:

ok single line: '11 2'

Test #10:

score: 0
Accepted
time: 3ms
memory: 56448kb

input:

4 4 3
1 2 E 4 1 W
2 3 2 4 1
5 1 1 2 1 1 3 3 2 3 3

output:

5 2

result:

ok single line: '5 2'

Test #11:

score: 0
Accepted
time: 0ms
memory: 56520kb

input:

10 10 2
1 1 E 6 1 W
1 6 1
1 1 1

output:

8 4

result:

ok single line: '8 4'

Test #12:

score: 0
Accepted
time: 4ms
memory: 56488kb

input:

10 10 2
1 1 E 3 1 W
3 5 5 5 6 5 7
3 9 8 9 7 9 6

output:

6 1

result:

ok single line: '6 1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 56452kb

input:

4 8 2
2 4 S 2 6 S
1 2 2
1 2 5

output:

8 1

result:

ok single line: '8 1'

Test #14:

score: 0
Accepted
time: 7ms
memory: 56480kb

input:

5 10 1
3 2 E 5 2 E
2 3 2 5 2
2 1 1 1 2

output:

9 3

result:

ok single line: '9 3'

Test #15:

score: 0
Accepted
time: 4ms
memory: 56736kb

input:

10 10 2
2 3 S 3 3 E
4 2 1 3 1 2 2 3 2
3 1 2 2 2 3 2

output:

11 2

result:

ok single line: '11 2'

Test #16:

score: 0
Accepted
time: 0ms
memory: 56536kb

input:

1 5 1
1 2 S 1 3 S
1 1 4
0

output:

3 0

result:

ok single line: '3 0'

Test #17:

score: 0
Accepted
time: 874ms
memory: 59956kb

input:

50 50 49
14 39 N 30 28 N
50 1 3 30 21 26 11 32 37 7 14 46 49 44 46 17 16 46 38 42 25 7 9 38 29 22 15 6 20 20 34 49 7 48 27 19 18 27 8 29 17 22 41 11 8 6 43 20 29 13 47 14 46 31 43 18 43 40 28 39 35 2 13 31 47 23 35 37 46 3 1 18 11 9 39 31 22 28 12 15 14 24 23 35 47 16 3 13 19 35 5 6 30 18 46 44 2 30...

output:

74 0

result:

ok single line: '74 0'

Test #18:

score: 0
Accepted
time: 904ms
memory: 59316kb

input:

50 50 28
39 24 W 50 30 N
48 4 35 19 38 23 43 12 49 26 35 20 40 24 9 29 41 2 16 23 36 26 40 45 5 31 10 41 49 34 44 39 4 2 8 40 11 10 40 10 13 18 6 18 28 2 4 17 22 41 38 20 29 6 35 35 20 42 47 32 21 20 38 17 33 42 45 21 4 39 32 49 32 26 3 11 28 12 6 28 47 2 42 29 14 22 23 34 40 47 23 47 26 39 16 1 17
...

output:

67 29

result:

ok single line: '67 29'

Test #19:

score: 0
Accepted
time: 927ms
memory: 59324kb

input:

50 50 31
17 31 S 9 3 S
48 43 19 48 37 39 21 27 23 9 22 35 3 35 15 15 20 18 2 48 3 8 25 28 44 33 23 36 21 49 27 22 12 34 14 30 32 25 17 45 38 41 36 3 17 47 18 34 17 4 38 20 28 21 41 17 6 11 10 1 11 8 41 43 32 30 9 11 2 2 29 3 46 39 20 34 5 29 22 38 3 11 32 8 29 2 33 10 19 37 3 47 37 1 9 29 27
48 18 4...

output:

53 8

result:

ok single line: '53 8'

Test #20:

score: 0
Accepted
time: 878ms
memory: 59116kb

input:

50 50 35
47 40 N 20 27 N
50 38 4 24 32 7 49 46 46 35 15 5 10 2 21 6 48 38 31 25 24 34 16 16 34 41 6 40 37 8 9 11 28 29 18 13 12 5 18 32 40 17 11 38 28 31 8 13 31 41 10 42 23 27 4 28 20 40 49 8 25 33 13 11 49 15 30 14 27 15 22 31 10 10 6 30 3 42 7 46 16 14 1 37 17 8 17 24 2 41 11 35 14 46 45 26 21 12...

output:

68 18

result:

ok single line: '68 18'

Test #21:

score: 0
Accepted
time: 0ms
memory: 56444kb

input:

10 10 1
3 1 N 3 2 N
0
81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2 6...

output:

42 4

result:

ok single line: '42 4'

Test #22:

score: 0
Accepted
time: 4ms
memory: 56720kb

input:

4 4 1
4 1 N 4 2 N
0
9 1 1 1 2 1 3 2 2 2 3 2 4 3 1 3 2 3 3

output:

24 4

result:

ok single line: '24 4'

Test #23:

score: 0
Accepted
time: 4ms
memory: 56480kb

input:

50 50 1
1 50 N 50 50 E
0
0

output:

100 1

result:

ok single line: '100 1'

Test #24:

score: 0
Accepted
time: 315ms
memory: 57844kb

input:

50 50 28
39 24 W 50 30 N
0
1 40 17

output:

67 28

result:

ok single line: '67 28'

Test #25:

score: 0
Accepted
time: 23ms
memory: 56880kb

input:

25 25 14
19 12 W 25 15 N
0
1 20 8

output:

34 13

result:

ok single line: '34 13'

Test #26:

score: 0
Accepted
time: 12ms
memory: 56536kb

input:

25 16 14
19 9 W 25 12 N
0
1 20 5

output:

31 13

result:

ok single line: '31 13'

Test #27:

score: 0
Accepted
time: 3ms
memory: 56740kb

input:

12 16 1
6 9 W 12 12 N
0
1 7 5

output:

31 13

result:

ok single line: '31 13'