oj.uz

Submission #869005

# Submission time Handle Problem Language Result Execution time Memory
869005 2023-11-02T23:11:34 Z bobbilyking Tracks in the Snow (BOI13_tracks) C++17
69.7917 / 100
 598 ms 499784 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}}, nq;
    char cur = grid[0][0]; // character we are currently looking at
    ll iter = 0;
    vis[0][0] = 1;
    for (; q.size(); iter++, swap(q, nq), nq.clear(), cur = cur == 'R' ? 'F' : 'R') {
        F(ha, 0, q.size()) {
            const 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);
                }
            }
        }
    }
    // F(i, 0, h) {
    //     F(j, 0, w) {
    //         cout << vis[i][j];
    //     }
    //     cout << endl;
    // }

    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)
......
   44 |         F(ha, 0, q.size()) {
      |           ~~~~~~~~~~~~~~~              
tracks.cpp:44:9: note: in expansion of macro 'F'
   44 |         F(ha, 0, q.size()) {
      |         ^

Subtask #1
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3548 KB Output isn't correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Runtime error 5 ms 5972 KB Execution killed with signal 11
5 Correct 2 ms 1932 KB Output is correct
6 Correct 0 ms 584 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Runtime error 5 ms 3928 KB Execution killed with signal 11
12 Correct 4 ms 2292 KB Output is correct
13 Correct 2 ms 1716 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Incorrect 7 ms 3556 KB Output isn't correct
17 Correct 5 ms 2900 KB Output is correct
18 Runtime error 5 ms 6100 KB Execution killed with signal 11

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15704 KB Output is correct
2 Incorrect 26 ms 8796 KB Output isn't correct
3 Correct 113 ms 49792 KB Output is correct
4 Correct 37 ms 15700 KB Output is correct
5 Correct 62 ms 31060 KB Output is correct
6 Runtime error 42 ms 53968 KB Execution killed with signal 11
7 Correct 9 ms 16220 KB Output is correct
8 Correct 7 ms 15708 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 7 ms 15964 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Incorrect 26 ms 8792 KB Output isn't correct
14 Incorrect 15 ms 5976 KB Output isn't correct
15 Correct 8 ms 6488 KB Output is correct
16 Correct 12 ms 3672 KB Output is correct
17 Correct 73 ms 17068 KB Output is correct
18 Correct 36 ms 16464 KB Output is correct
19 Correct 37 ms 15700 KB Output is correct
20 Correct 30 ms 14424 KB Output is correct
21 Correct 90 ms 32328 KB Output is correct
22 Correct 61 ms 31016 KB Output is correct
23 Correct 145 ms 26520 KB Output is correct
24 Correct 66 ms 31664 KB Output is correct
25 Correct 181 ms 49744 KB Output is correct
26 Correct 333 ms 304308 KB Output is correct
27 Runtime error 598 ms 499784 KB Execution killed with signal 11
28 Runtime error 40 ms 53964 KB Execution killed with signal 11
29 Runtime error 45 ms 53940 KB Execution killed with signal 11
30 Runtime error 40 ms 53192 KB Execution killed with signal 11
31 Runtime error 29 ms 39484 KB Execution killed with signal 11
32 Runtime error 67 ms 84100 KB Execution killed with signal 11