oj.uz

Submission #817874

# Submission time Handle Problem Language Result Execution time Memory
817874 2023-08-09T18:29:35 Z Ozy Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 62 ms 17208 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a <<  " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli> 

#define MAX 200000

lli dir[8] = {0,0,1,-1,-1,1,0,0};
lli vis[4][MAX+2];
lli acu[3][MAX+2],inval[3][MAX+2];
lli fil,col,res;

void dfs(pll pos,lli id) {

    queue<pll> cola;
    cola.push(pos);
    vis[pos.first][pos.second] = id;

    pll n_pos;
    while (!cola.empty()) {
        pos = cola.front();
        cola.pop();


        rep(i,0,3) {
            n_pos.first = pos.first + dir[i];
            n_pos.second = pos.second + dir[i+4];

            if(vis[n_pos.first][n_pos.second]) continue;

            vis[n_pos.first][n_pos.second] = id;
            cola.push(n_pos); 
        }

    }

}

//solucion subtask #2
void init(int R, int C, int sr, int sc, int M, char *S) {
    fil = R;
    col = C;
    rep(j,0,col+1) {
        vis[0][j] = 1;
        vis[3][j] = 1;
    }   
    rep(i,0,3) {
        vis[i][0] = 1;
        vis[i][col+1] = 1;
    }

    pll pos = {sr,sc};
    rep(i,0,M-1) {
        vis[pos.first][pos.second] = 1;
        if (S[i] == 'N') pos.first--;
        if (S[i] == 'S') pos.first++;
        if (S[i] == 'W') pos.second--;
        if (S[i] == 'E') pos.second++;
    }
    vis[pos.first][pos.second] = 1;

    //hacer los acululados individuales
    rep(i,1,2) {
        rep(j,1,col) {
            acu[i][j] = acu[i][j-1];
            if (vis[i][j] == 1) {inval[i][j] = 1; continue;}
            if (vis[i][j-1] == 1) {
                inval[i][j] = 1;
                acu[i][j]++;
            }
        }   
    }

    //marcar los que son invalidos para el R = 2
    inval[0][0] = 1;
    rep(j,1,col) if(vis[1][j] && vis[2][j]) inval[0][j] = 1;

    //hacer los acumulados
    rep(j,1,col) {
        acu[0][j] = acu[0][j-1];
        if (vis[1][j] == 0) {
            inval[0][j] = 1;
            acu[0][j]++;
            dfs({1,j},acu[0][j]);
        } 
        if (vis[2][j] == 0) {
            inval[0][j] = 1;
            acu[0][j]++;
            dfs({2,j},acu[0][j]);
        } 
    }

    //cout << endl;
    //rep(i,0,2){
    //    rep(j,1,col) cout << acu[i][j];
    //    cout << endl; 
    //}
}
//poner tambien que los inicios son invalidos

int colour(int ar, int ac, int br, int bc) {
    lli a;

    if (ar != br) a = 0;
    else a = ar;

    //debugsl(acu[a][bc]);
    //debug(acu[a][ac-1]);

    lli res = acu[a][bc] - acu[a][ac-1];
    if (!inval[a][ac]) res++;
    return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 52 ms 15312 KB Output is correct
4 Correct 55 ms 17140 KB Output is correct
5 Correct 57 ms 16988 KB Output is correct
6 Correct 55 ms 16032 KB Output is correct
7 Correct 50 ms 16088 KB Output is correct
8 Correct 62 ms 14968 KB Output is correct
9 Correct 53 ms 17208 KB Output is correct
10 Correct 56 ms 16932 KB Output is correct
11 Correct 53 ms 16040 KB Output is correct
12 Correct 47 ms 15700 KB Output is correct
13 Correct 47 ms 17104 KB Output is correct
14 Correct 48 ms 16956 KB Output is correct
15 Correct 48 ms 16076 KB Output is correct
16 Correct 54 ms 15516 KB Output is correct

Subtask #3
0 / 24.0

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