oj.uz

Submission #1116745

# Submission time Handle Problem Language Result Execution time Memory
1116745 2024-11-22T10:17:08 Z OI_Account Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 72 ms 4972 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 37 ms 532 KB Output is correct
3 Correct 47 ms 592 KB Output is correct
4 Correct 47 ms 760 KB Output is correct
5 Correct 41 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 38 ms 556 KB Output is correct
12 Correct 43 ms 584 KB Output is correct
13 Correct 72 ms 336 KB Output is correct
14 Correct 67 ms 548 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 444 KB Output is correct
17 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 32 ms 4588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 37 ms 532 KB Output is correct
3 Correct 47 ms 592 KB Output is correct
4 Correct 47 ms 760 KB Output is correct
5 Correct 41 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 38 ms 556 KB Output is correct
12 Correct 43 ms 584 KB Output is correct
13 Correct 72 ms 336 KB Output is correct
14 Correct 67 ms 548 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 444 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 34 ms 4972 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 37 ms 532 KB Output is correct
3 Correct 47 ms 592 KB Output is correct
4 Correct 47 ms 760 KB Output is correct
5 Correct 41 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 38 ms 556 KB Output is correct
12 Correct 43 ms 584 KB Output is correct
13 Correct 72 ms 336 KB Output is correct
14 Correct 67 ms 548 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 444 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 34 ms 4972 KB Output isn't correct
19 Halted 0 ms 0 KB -