oj.uz

Submission #1117133

# Submission time Handle Problem Language Result Execution time Memory
1117133 2024-11-22T20:58:41 Z gustavo_d Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 51 ms 4444 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

map<char, pair<int, int>> ds;
pair<int, int> moves[4] = {
    {0, -1},
    {0, 1},
    {1, 0},
    {-1, 0},
};

bool mark[51][51];
bool mark2[3][200001];

int x, y;

// TODO: cout de debug que some ao submeter
vector<pair<int, int>> r1, r2, r12;
void init(int R, int C, int sr, int sc, int M, char *S) {
    x=R; y=C;
    ds['N'] = {-1, 0};
    ds['S'] = {1, 0};
    ds['E'] = {0, 1};
    ds['W'] = {0, -1};
    if (R == 2) {
        mark2[sr][sc] = true;
        // cout << sr << ' ' << sc << endl;
        for (int i=0; i<M; i++) {
            char c = S[i];
            sr += ds[c].first;
            sc += ds[c].second;
            mark2[sr][sc] = true;
            // cout << sr << ' ' << sc << endl;
        }
        pair<int, int> rng = {-1, -1};
        for (int i=1; i<=C; i++) {
            if (mark2[1][i]) {
                if (rng.first != -1) {
                    r1.push_back(rng);
                }
                rng = {-1, -1};
            } else {
                if (rng.first == -1) rng = {i, i};
                else rng.second++;
            }
        }
        if (rng.first != -1) {
            r1.push_back(rng);
        }

        rng = {-1, -1};
        for (int i=1; i<=C; i++) {
            if (mark2[2][i]) {
                if (rng.first != -1) {
                    r2.push_back(rng);
                }
                rng = {-1, -1};
            } else {
                if (rng.first == -1) rng = {i, i};
                else rng.second++;
            }
        }
        if (rng.first != -1) {
            r2.push_back(rng);
        }

        rng = {-1, -1};
        for (int i=1; i<=C; i++) {
            if (mark2[1][i] and mark2[2][i]) {
                if (rng.first != -1) {
                    r12.push_back(rng);
                }
                rng = {-1, -1};
            } else {
                if (rng.first == -1) rng = {i, i};
                else rng.second++;
            }
        }
        if (rng.first != -1) {
            r12.push_back(rng);
        }
        // for (pair<int, int> rn : r1) cout << "1: " << rn.first << ' ' << rn.second << endl;
        // for (pair<int, int> rn : r2) cout << "2: " << rn.first << ' ' << rn.second << endl;
        // for (pair<int, int> rn : r12) cout << "1, 2: " << rn.first << ' ' << rn.second << endl;
        return;
    }
    for (int i=0; i<=50; i++) mark[i][0] = true;
    for (int i=0; i<=50; i++) mark[0][i] = true;
    mark[sr][sc] = true;
    // cout << sr << ' ' << sc << endl;
    for (int i=0; i<M; i++) {
        char c = S[i];
        sr += ds[c].first;
        sc += ds[c].second;
        mark[sr][sc] = true;
        // cout << sr << ' ' << sc << endl;
    }
}

bool tmp[51][51];
int lar, lac, lbr, lbc;
void dfs(int i, int j) {
    if (i < lar or j < lac or i > lbr or j > lbc or tmp[i][j]) return;
    tmp[i][j] = true;
    for (pair<int, int> d : moves) {
        dfs(i + d.first, j + d.second);
    }
}

int solve(vector<pair<int, int>> &rngs, int l, int r) {
    auto fi = lower_bound(rngs.begin(), rngs.end(), make_pair(l, 0));
    if (fi != rngs.begin()) {
        fi--;
        if ((fi->second) < l) fi++;
    }
    if (fi == rngs.end()) return 0;
    auto last = upper_bound(rngs.begin(), rngs.end(), make_pair(r, (int)1e9));
    if (last == rngs.begin()) return 0;
    last--;
    return distance(fi, last) + 1;
}

int colour(int ar, int ac, int br, int bc) {
    if (x == 2) {
        if (ar == 1 and br == 1) {
            // cout << "caso 1" << endl;
            return solve(r1, ac, bc);
        }
        if (ar == 2 and br == 2) {
            // cout << "caso 2" << endl;
            return solve(r2, ac, bc);
        }
        if (ar == 1 and br == 2) {
            // cout << "caso 1, 2" << endl;
            return solve(r12, ac, bc);
        }
    }

    lar = ar; lac = ac; lbr = br; lbc = bc;
    int cnt = 0;

    for (int i=1; i<=50; i++) {
        for (int j=1; j<=50; j++) {
            tmp[i][j] = mark[i][j];
        }
    }
    for (int r=ar; r<=br; r++) {
        for (int c=ac; c<=bc; c++) {
            if (!tmp[r][c]) {
                cnt++;
                dfs(r, c);
            }
        }
    }
    return cnt;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 33 ms 1104 KB Output is correct
4 Correct 41 ms 1360 KB Output is correct
5 Correct 43 ms 4444 KB Output is correct
6 Correct 38 ms 1412 KB Output is correct
7 Correct 41 ms 1876 KB Output is correct
8 Correct 35 ms 3920 KB Output is correct
9 Correct 39 ms 1376 KB Output is correct
10 Correct 42 ms 1608 KB Output is correct
11 Correct 51 ms 4424 KB Output is correct
12 Correct 40 ms 3656 KB Output is correct
13 Correct 48 ms 4176 KB Output is correct
14 Correct 36 ms 1616 KB Output is correct
15 Correct 41 ms 4428 KB Output is correct
16 Correct 33 ms 1096 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 2 ms 592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 11 ms 336 KB Output is correct
4 Correct 11 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 9 ms 336 KB Output is correct
12 Correct 7 ms 336 KB Output is correct
13 Correct 6 ms 336 KB Output is correct
14 Correct 4 ms 464 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Runtime error 2 ms 592 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 11 ms 336 KB Output is correct
4 Correct 11 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 9 ms 336 KB Output is correct
12 Correct 7 ms 336 KB Output is correct
13 Correct 6 ms 336 KB Output is correct
14 Correct 4 ms 464 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Runtime error 2 ms 592 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -