oj.uz

Submission #1117122

# Submission time Handle Problem Language Result Execution time Memory
1117122 2024-11-22T20:45:48 Z hyakup Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 73 ms 27592 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;


const int maxn = 2e5 + 10;
const int inf = 1e9;

int marc[4][maxn], sum[4][maxn], head[4][maxn];
int n, m, q;

int di[] = { 0, 1, 0, -1 };
int dj[] = { 1, 0, -1, 0 };
int linha1, linha2, coluna1, coluna2;

bool in_bounds( int i, int j ){
    return linha1 <= i && i <= linha2 && coluna1 <= j && j <= coluna2;
}


void dfs( int i, int j ){
    // bug(i);
    // bug(j);
    marc[i][j] = q;
    for( int d = 0; d < 4; d++ ) if( marc[i + di[d]][j + dj[d]] < q && in_bounds( i + di[d], j + dj[d] ) ) dfs( i + di[d], j + dj[d] );
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    // bug(R);
    coluna1 = 1, coluna2 = m;
    marc[sr][sc] = inf;
    for( int i = 0; i < M; i++ ){
        char c = S[i];
        if( c == 'N' ) sr--;
        if( c == 'S' ) sr++;
        if( c == 'W' ) sc--;
        if( c == 'E' ) sc++;

        marc[sr][sc] = inf;
    }

    for( int i = 1; i <= 2; i++ ){
        // cout << "sla " << endl;
        linha1 = linha2 = i;
        for( int j = m; j > 0; j-- ){
            if( !marc[i][j] ){
                q = j;
                dfs( i, j );
            }

        }
        for( int j = 1;j <= m; j++ ){
            sum[i][j] = sum[i][j - 1] + (( marc[i][j] == j ) ? 1 : 0 );
            head[i][j] = marc[i][j];
            if( marc[i][j] != inf ) marc[i][j] = 0;
            // bug(sum[i][j]);
        }
    }

    linha1 = 1; linha2 = 2;
    for( int j = m; j > 0; j-- ) for( int i = 1;i <= 2; i++ ){
        if( !marc[i][j] ){
            q = j;
            dfs( i, j );
        }
    }

    for( int j = 1; j <= m; j++ ){
        sum[3][j] = sum[3][j - 1] + (( marc[1][j] == j || marc[2][j] == j ) ? 1 : 0 );
        if( marc[1][j] != inf ) head[3][j] = marc[1][j];
        else head[3][j] = marc[2][j];
        // bug(sum[3][j]);
    }

}



int colour(int ar, int ac, int br, int bc) {
    int id = (( ar < br ) ? 3 : ar );

    int resp = sum[id][bc] - sum[id][ac - 1];
    if( head[id][bc] > bc && head[id][bc] != inf ) resp++;
    return resp;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 66 ms 26096 KB Output is correct
4 Correct 58 ms 21576 KB Output is correct
5 Correct 65 ms 22344 KB Output is correct
6 Correct 67 ms 27380 KB Output is correct
7 Correct 56 ms 27464 KB Output is correct
8 Correct 59 ms 21196 KB Output is correct
9 Correct 52 ms 21556 KB Output is correct
10 Correct 59 ms 22564 KB Output is correct
11 Correct 73 ms 27464 KB Output is correct
12 Correct 59 ms 21320 KB Output is correct
13 Correct 51 ms 21576 KB Output is correct
14 Correct 55 ms 22344 KB Output is correct
15 Correct 62 ms 27592 KB Output is correct
16 Correct 69 ms 24904 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4604 KB Output is correct
2 Runtime error 2 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 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -