oj.uz

Submission #408579

# Submission time Handle Problem Language Result Execution time Memory
408579 2021-05-19T08:29:01 Z abc864197532 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#include "rainbow-grader.cpp"
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
// const int mod = 998244353, N = 1000001, logN = 20, K = 111;

vv <bool> area;
int n, m;

void init(int _n, int _m, int r, int c, int k, char *s) {
    r--, c--;
    n = _n, m = _m;
    area = vv<bool>(n, m, false);
    area[r][c] = true;
    for (int i = 0; i < k; ++i) {
        if (s[i] == 'W') c--;
        if (s[i] == 'E') c++;
        if (s[i] == 'N') r--;
        if (s[i] == 'S') r++;
        area[r][c] = true;
    }
}

int colour(int l1, int r1, int l2, int r2) {
    l1--, r1--;
    vv <bool> vis = area;
    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
    function<void(int, int)> bfs = [&](int a, int b) {
        queue <pii> q;
        q.emplace(a, b);
        vis[a][b] = true;
        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front(); q.pop();
            test(x, y);
            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (l1 <= nx && nx < l2 && r1 <= ny && ny < r2) if (!vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.emplace(nx, ny);
                }
            }
        }
    };
    int ans = 0;
    for (int i = l1; i < l2; ++i) for (int j = r1; j < r2; ++j) {
        if (vis[i][j]) continue;
        bfs(i, j);
        ans++;
    }
    return ans;
}

/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
 */

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 20 ms 332 KB Output is correct
3 Correct 37 ms 328 KB Output is correct
4 Correct 38 ms 320 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 31 ms 340 KB Output is correct
12 Correct 28 ms 312 KB Output is correct
13 Correct 23 ms 344 KB Output is correct
14 Correct 30 ms 320 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 3068 ms 696 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 489 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 20 ms 332 KB Output is correct
3 Correct 37 ms 328 KB Output is correct
4 Correct 38 ms 320 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 31 ms 340 KB Output is correct
12 Correct 28 ms 312 KB Output is correct
13 Correct 23 ms 344 KB Output is correct
14 Correct 30 ms 320 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3082 ms 1108 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 20 ms 332 KB Output is correct
3 Correct 37 ms 328 KB Output is correct
4 Correct 38 ms 320 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 31 ms 340 KB Output is correct
12 Correct 28 ms 312 KB Output is correct
13 Correct 23 ms 344 KB Output is correct
14 Correct 30 ms 320 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3082 ms 1108 KB Time limit exceeded
19 Halted 0 ms 0 KB -