Submission #817874

#	Time	Username	Problem	Language	Result	Execution time	Memory
817874		Ozy	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	62 ms	17208 KiB

rainbow

#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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26