oj.uz

Submission #545815

# Submission time Handle Problem Language Result Execution time Memory
545815 2022-04-05T13:43:43 Z Monarchuwu Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 69 ms 4944 KB 
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 2e5 + 8;
const int dr[4] = { 0, 0, 1, -1 };
const int dc[4] = { 1, -1, 0, 0 };
int r, c, m, q, sr, sc;
int num[256];
string s;

namespace subtask1 {
    bool vis_init[52][52], vis[52][52];
    void init() {
        vis_init[sr][sc] = true;
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis_init[sr][sc] = true;
        }
    }
    void dfs(int i, int j) {
        vis[i][j] = true;
        for (int k = 0, i2, j2; k < 4; ++k) {
            i2 = i + dr[k], j2 = j + dc[k];
            if (!vis[i2][j2]) dfs(i2, j2);
        }
    }
    int solve(int ar, int ac, int br, int bc) {
        int m = br - ar + 1, n = bc - ac + 1;
        for (int i = 1; i <= m; ++i) vis[i][0] = vis[i][n + 1] = true;
        for (int j = 1; j <= n; ++j) vis[0][j] = vis[m + 1][j] = true;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                vis[i][j] = vis_init[i + ar - 1][j + ac - 1];

        int cnt(0);
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (!vis[i][j]) dfs(i, j), ++cnt;
        return cnt;
    }
}

namespace subtask2 {
    bool vis[4][N];
    int prf[4][N];
    void init() {
        vis[1][0] = vis[2][0] = vis[sr][sc] = true;
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis[sr][sc] = true;
        }
        for (int i = 1; i <= c; ++i) {
            prf[1][i] = prf[1][i - 1] + (vis[1][i - 1] && !vis[1][i]);
            prf[2][i] = prf[2][i - 1] + (vis[2][i - 1] && !vis[2][i]);
            prf[3][i] = prf[3][i - 1] + (vis[1][i - 1] && vis[2][i - 1] && (!vis[1][i] || !vis[2][i]));
        }
    }
    int solve(int ar, int ac, int br, int bc) {
        if (ar == br) {
            return prf[ar][bc] - prf[ar][ac - 1] + (!vis[ar][ac - 1] && !vis[ar][ac]);
        }
        else {
            return prf[3][bc] - prf[3][ac - 1] + ((!vis[1][ac - 1] || !vis[2][ac - 1]) && (!vis[1][ac] || !vis[2][ac]));
        }
    }
}

void init(int R, int C, int SR, int SC, int M, char *S) {
    num['E'] = 0, num['W'] = 1, num['S'] = 2, num['N'] = 3;
    r = R, c = C, sr = SR, sc = SC, m = M;
    for (int i = 0; i < m; ++i) s.push_back(S[i]);
    if (r <= 50 && c <= 50)
        subtask1::init();
    else if (r == 2)
        subtask2::init();
}

int colour(int ar, int ac, int br, int bc) {
    if (r <= 50 && c <= 50)
        return subtask1::solve(ar, ac, br, bc);
    else if (r == 2)
        return subtask2::solve(ar, ac, br, bc);
    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message

rainbow.cpp: In function 'void subtask1::init()':
rainbow.cpp:22:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:23:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'void subtask2::init()':
rainbow.cpp:56:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:57:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |             sc += dc[num[c]];
      |                          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 61 ms 3548 KB Output is correct
4 Correct 69 ms 4848 KB Output is correct
5 Correct 55 ms 4824 KB Output is correct
6 Correct 56 ms 4784 KB Output is correct
7 Correct 52 ms 4684 KB Output is correct
8 Correct 55 ms 4612 KB Output is correct
9 Correct 57 ms 4768 KB Output is correct
10 Correct 56 ms 4744 KB Output is correct
11 Correct 53 ms 4692 KB Output is correct
12 Correct 49 ms 4748 KB Output is correct
13 Correct 52 ms 4944 KB Output is correct
14 Correct 56 ms 4824 KB Output is correct
15 Correct 52 ms 4668 KB Output is correct
16 Correct 57 ms 4796 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 50 ms 1236 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 50 ms 1236 KB Output isn't correct
19 Halted 0 ms 0 KB -