oj.uz

Submission #900237

# Submission time Handle Problem Language Result Execution time Memory
900237 2024-01-07T23:56:18 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 14 ms 964 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int,int>

const int N = 55;
int grid[N][N];
int rows, cols;

map<char,ii> to = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}};

int arriba[N], abajo[N], ambos[N];

void init(int R, int C, int sr, int sc, int M, char *s){
    rows = R;
    cols = C;
    sr--, sc--;

    ii pos = {sr, sc};
    grid[pos.first][pos.second] = 1;
    for(int i=0; i<M; ++i){
        char c = s[i];
        pos.first += to[c].first;
        pos.second += to[c].second;
        grid[pos.first][pos.second] = 1;
    }

    // if(rows == 2){
    //     // subtask 2
    //     arriba[0] = (grid[0][0] != 1);
    //     abajo[0] = (grid[1][0] != 1);
    //     for(int i=1; i<cols; ++i){
    //         arriba[i] = (grid[0][i-1] == 1 && grid[0][i] == 0);
    //         abajo[i] = (grid[1][i-1] == 1 && grid[1][i] == 0);
    //     }
    //     for(int i=1; i<cols; ++i){
    //         arriba[i] += arriba[i-1];
    //         abajo[i] += abajo[i-1];
    //     }
    //     // ambos
    //     ambos[0] = (grid[0][0] == 0 or grid[1][0] == 0);
    //     for(int i=1; i<cols; ++i){
    //         if(grid[0][i-1] == 1 && grid[1][i-1] == 1){
    //             ambos[i] = (grid[0][i] == 0 or grid[1][i] == 0);
    //         }
    //     }
    //     for(int i=1; i<cols; ++i){
    //         ambos[i] += ambos[i-1];
    //     }
    // }

}

void clear(){
    for(int i=0; i<rows; ++i){
        for(int j=0; j<cols; ++j){
            if(grid[i][j] == 2) grid[i][j] = 0;
        }
    }
}

vector<ii> mov = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void dfs(int i, int j, int ar, int ac, int br, int bc){
    for(auto tmp : mov){
        int ni = i + tmp.first;
        int nj = j + tmp.second;
        if(ni >= ar && ni <= br && nj >= ac && nj <= bc && grid[ni][nj] == 0){
            grid[ni][nj] = 2;
            dfs(ni, nj, ar, ac, br, bc);
        }
    }
}

int colour(int ar, int ac, int br, int bc){

    ar--, ac--;
    br--, bc--;

    // if(rows == 2){
    //     // subtask 2
    //     if(ar+1 == br){
    //         // ambos
    //         int res = ambos[bc];
    //         if(ac > 0){
    //             res -= ambos[ac-1];
    //         }
    //         return res;
    //     }
    //     // arriba
    //     if(ar == 0){
    //         int res = arriba[bc];
    //         if(ac > 0){
    //             res -= arriba[ac-1];
    //         }
    //         return res;
    //     }
    //     // abajo
    //     assert(ar == 1);
    //     int res = abajo[bc];
    //     if(ac > 0){
    //         res -= abajo[ac-1];
    //     }
    //     return res;
    // }

    // subtask 1
    int ans = 0;
    for(int i=ar; i<=br; ++i){
        for(int j=ac; j<=bc; ++j){
            if(grid[i][j] == 0){
                ans++;
                grid[i][j] = 2;
                dfs(i, j, ar, ac, br, bc);
            }
        }
    }
    clear();
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 14 ms 604 KB Output is correct
4 Correct 11 ms 608 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 10 ms 584 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 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 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 14 ms 604 KB Output is correct
4 Correct 11 ms 608 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 10 ms 584 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 2 ms 964 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 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 14 ms 604 KB Output is correct
4 Correct 11 ms 608 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 10 ms 584 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 2 ms 964 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -