Submission #1116754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116754		OI_Account	Land of the Rainbow Gold (APIO17_rainbow)	C++17	23 / 100	131 ms	25580 KiB

rainbow

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

const int N = 200'000;
const int D = 4;
const int DX[D] = {0, 0, -1, 1};
const int DY[D] = {-1, 1, 0, 0};

int n, m, a, b, x1, yyy, x2, y2;
vector<pair<int, int>> path;
vector<char> vecDir = {'W', 'E', 'N', 'S'};
int markSub1[60][60], cnt[3][N + 10], cmpSub2;
int markSub2[3][N + 10], valSub2[N + 10];

void uniquePath() {
    sort(path.begin(), path.end());
    path.resize(unique(path.begin(), path.end()) - path.begin());
}

bool isSub1() {
    return max(n, m) <= 50;
}

bool inPath(int x, int y) {
    int idx = lower_bound(path.begin(), path.end(), make_pair(x, y)) - path.begin();
    return idx < path.size() && path[idx] == make_pair(x, y);
}

bool inSub(int a, int b) {
    bool checkA = (x1 <= a && a <= x2);
    bool checkB = (yyy <= b && b <= y2);
    return checkA && checkB;
}

void initSub1() {
    uniquePath();
}

bool isSub2() {
    return n <= 2 && m <= N;
}

bool inGrid(int x, int y) {
    return min(x, y) >= 1 && x <= n && y <= m;
}

void dfs2(int i, int j) {
    markSub2[i][j] = cmpSub2;
    for (int d = 0; d < D; d++) {
        int nx = i + DX[d];
        int ny = j + DY[d];
        if (inGrid(nx, ny) && !inPath(nx, ny) && !markSub2[nx][ny])
            dfs2(nx, ny);
    }
}

void initSub2() {
    uniquePath();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cnt[i][j] = cnt[i][j - 1];
            if ((j == 1 || inPath(i, j - 1)) && !inPath(i, j))
                cnt[i][j]++;
        }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++)
            if (!inPath(i, j) && !markSub2[i][j]) {
                cmpSub2++;
                dfs2(i, j);
            }
        valSub2[j] = cmpSub2;
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R;
    m = C;
    a = sr;
    b = sc;
    path.push_back({a, b});
    for (int i = 0; i < M; i++) {
        int idx;
        for (int j = 0; j < D; j++)
            if (S[i] == vecDir[j])
                idx = j;
        int nx = path.back().first + DX[idx];
        int ny = path.back().second + DY[idx];
        path.push_back({nx, ny});
    }
    if (isSub1())
        initSub1();
    else if (isSub2())
        initSub2();
}

void dfs(int i, int j) {
    markSub1[i][j] = true;
    for (int d = 0; d < D; d++) {
        int nx = i + DX[d];
        int ny = j + DY[d];
        if (inSub(nx, ny) && !inPath(nx, ny) && !markSub1[nx][ny])
            dfs(nx, ny);
    }
}

int solveSub1() {
    for (int i = x1; i <= x2; i++)  
        for (int j = yyy; j <= y2; j++)
            markSub1[i][j] = 0;
    int ans = 0;
    for (int i = x1; i <= x2; i++)
        for (int j = yyy; j <= y2; j++)
            if (!inPath(i, j) && !markSub1[i][j]) {
                ans++;
                dfs(i, j);
            }
    return ans;
}

int solveSub2() {
    if (x1 == x2)
        return cnt[x2][y2] - cnt[x2][yyy] + (!inPath(x2, yyy));
    bool add = false;
    for (int i = 1; i <= n; i++)
        if (!inPath(i, yyy))
            add = true;
    return valSub2[y2] - valSub2[yyy] + add;
}

int colour(int ar, int ac, int br, int bc) {
    x1 = ar;
    yyy = ac;
    x2 = br;
    y2 = bc;
    if (isSub1())
        return solveSub1();
    if (isSub2())
        return solveSub2();
    return 0;
}

Compilation message (stderr)

rainbow.cpp: In function 'bool inPath(int, int)':
rainbow.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     return idx < path.size() && path[idx] == make_pair(x, y);
      |            ~~~~^~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:88:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |         int ny = path.back().second + DY[idx];
      |                                       ~~~~~~^

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26