oj.uz

답안 #869006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869006 2023-11-02T23:17:31 Z bobbilyking Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 604 ms 358288 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN
#define M 1000000007 // 998244353

string grid[4010];
bool vis[4010][4010];
int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(h) G(w)
    F(i, 0, h) cin >> grid[i];

    ll dx[4] = {0, -1, 0, 1};
    ll dy[4] = {1, 0, -1, 0};

    vector<pl> q{pl{0, 0}, pl{h-1, w-1}};
    vector<pl> nq;
    char cur = grid[0][0]; // character we are currently looking at
    ll iter = 0;
    vis[0][0] = vis[h-1][w-1] = 1;
    
    for (; q.size(); iter++, cur = cur == 'R' ? 'F' : 'R') {
        F(ha, 0, q.size()) {
            auto [x, y] = q[ha];
            F(k, 0, 4) {
                ll ni = x + dx[k], nj = y + dy[k];
                if (min(ni, nj) >= 0 and ni < h and nj < w and grid[ni][nj] != '.' and !vis[ni][nj]) {
                    vis[ni][nj] = 1;
                    if (grid[ni][nj] == cur) q.emplace_back(ni, nj);
                    else nq.emplace_back(ni, nj);
                }
            }
        }
        q.clear(); swap(q, nq);
    }

    cout << iter << '\n';
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:20:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define F(i, l, r) for (ll i = (l); i < r; ++i)
......
   46 |         F(ha, 0, q.size()) {
      |           ~~~~~~~~~~~~~~~              
tracks.cpp:46:9: note: in expansion of macro 'F'
   46 |         F(ha, 0, q.size()) {
      |         ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3588 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 5 ms 5844 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 6 ms 3372 KB Output is correct
16 Correct 7 ms 3592 KB Output is correct
17 Correct 5 ms 3164 KB Output is correct
18 Correct 5 ms 5848 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15452 KB Output is correct
2 Correct 24 ms 8760 KB Output is correct
3 Correct 105 ms 34000 KB Output is correct
4 Correct 33 ms 12888 KB Output is correct
5 Correct 54 ms 22876 KB Output is correct
6 Correct 597 ms 279288 KB Output is correct
7 Correct 8 ms 16220 KB Output is correct
8 Correct 8 ms 15560 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 7 ms 15964 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 24 ms 8540 KB Output is correct
14 Correct 14 ms 5976 KB Output is correct
15 Correct 8 ms 5720 KB Output is correct
16 Correct 12 ms 3676 KB Output is correct
17 Correct 70 ms 13596 KB Output is correct
18 Correct 30 ms 13144 KB Output is correct
19 Correct 34 ms 13096 KB Output is correct
20 Correct 32 ms 12636 KB Output is correct
21 Correct 69 ms 23128 KB Output is correct
22 Correct 54 ms 22872 KB Output is correct
23 Correct 143 ms 19668 KB Output is correct
24 Correct 65 ms 23040 KB Output is correct
25 Correct 167 ms 33972 KB Output is correct
26 Correct 337 ms 291704 KB Output is correct
27 Correct 479 ms 334792 KB Output is correct
28 Correct 555 ms 279372 KB Output is correct
29 Correct 604 ms 265720 KB Output is correct
30 Correct 496 ms 358288 KB Output is correct
31 Correct 397 ms 29460 KB Output is correct
32 Correct 384 ms 300424 KB Output is correct