oj.uz

Submission #545833

# Submission time Handle Problem Language Result Execution time Memory
545833 2022-04-05T14:25:42 Z Monarchuwu Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 34252 KB 
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
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[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dc[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
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]));
        }
    }
}

namespace subtask3 {
    set<pii> vis, arr_set;
    map<pii, int> mp;
    pii a[N << 2];
    void init() {
        vis.emplace(sr, sc);
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis.emplace(sr, sc);
        }

        arr_set = vis;
        for (pii x : arr_set) {
            for (int k = 0; k < 8; ++k) {
                pii p(x.ff + dr[k], x.ss + dc[k]);
                if (1 <= p.ff && p.ff <= r && 1 <= p.ss && p.ss <= c && vis.insert(p).ss)
                    a[mp[p] = mp.size() + 1] = p;
            }
        }
    }

    int par[N << 2];
    int root(int u) { return par[u] < 0 ? u : par[u] = root(par[u]); }
    bool Union(int u, int v) {
        if ((u = root(u)) == (v = root(v))) return false;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }

    int solve(int ar, int ac, int br, int bc) {
        int cnt(0);
        for (int i = 1; i <= mp.size(); ++i)
            par[i] = ar <= a[i].ff && a[i].ff <= br && ac <= a[i].ss && a[i].ss <= bc ? (++cnt, -1) : 0;

        // inside or outside
        if (cnt == 0) {
            for (pii p : arr_set) {
                if (ar <= p.ff <= br && ac <= p.ss && p.ss <= bc) return 1;
            }
            return 0;
        }

        for (int i = 1; i <= mp.size(); ++i) if (par[i]) {
            for (int k = 0; k < 4; ++k) {
                pii p = a[i];
                p.ff += dr[k];
                p.ss += dc[k];
                if (mp.count(p)) {
                    int j = mp[p];
                    if (par[j]) cnt -= Union(i, j);
                }
            }
        }
        return cnt;
    }
}

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();
    else
        subtask3::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);
    else
        return subtask3::solve(ar, ac, br, bc);
}

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

Compilation message

rainbow.cpp: In function 'void subtask1::init()':
rainbow.cpp:24:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:25:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'void subtask2::init()':
rainbow.cpp:58:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:59:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'void subtask3::init()':
rainbow.cpp:85:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:86:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'int subtask3::solve(int, int, int, int)':
rainbow.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int i = 1; i <= mp.size(); ++i)
      |                         ~~^~~~~~~~~~~~
rainbow.cpp:118:24: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  118 |                 if (ar <= p.ff <= br && ac <= p.ss && p.ss <= bc) return 1;
      |                        ^
rainbow.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 1; i <= mp.size(); ++i) if (par[i]) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 396 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 1 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 1 ms 212 KB Output is correct
3 Correct 55 ms 3612 KB Output is correct
4 Correct 53 ms 3820 KB Output is correct
5 Correct 54 ms 3740 KB Output is correct
6 Correct 53 ms 3712 KB Output is correct
7 Correct 54 ms 3652 KB Output is correct
8 Correct 52 ms 3660 KB Output is correct
9 Correct 51 ms 3848 KB Output is correct
10 Correct 53 ms 3796 KB Output is correct
11 Correct 53 ms 3740 KB Output is correct
12 Correct 49 ms 3788 KB Output is correct
13 Correct 50 ms 3788 KB Output is correct
14 Correct 51 ms 3828 KB Output is correct
15 Correct 50 ms 3840 KB Output is correct
16 Correct 55 ms 3728 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 Correct 298 ms 34168 KB Output is correct
3 Correct 216 ms 34124 KB Output is correct
4 Correct 287 ms 34252 KB Output is correct
5 Correct 166 ms 25696 KB Output is correct
6 Incorrect 32 ms 4008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 396 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 1 ms 212 KB Output is correct
18 Execution timed out 3071 ms 16868 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 396 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 1 ms 212 KB Output is correct
18 Execution timed out 3071 ms 16868 KB Time limit exceeded
19 Halted 0 ms 0 KB -