Submission #1116745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116745		OI_Account	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	72 ms	4972 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];

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();
}

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();
}

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 colour(int ar, int ac, int br, int bc) {
    x1 = ar;
    yyy = ac;
    x2 = br;
    y2 = bc;
    if (isSub1())
        return solveSub1();
    return 0;
}

Compilation message (stderr)

rainbow.cpp: In function 'bool inPath(int, int)':
rainbow.cpp:26: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]
   26 |     return idx < path.size() && path[idx] == make_pair(x, y);
      |            ~~~~^~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:51:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         int ny = path.back().second + DY[idx];
      |                                       ~~~~~~^

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