Submission #1170680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170680		stdfloat	Land of the Rainbow Gold (APIO17_rainbow)	C++20	12 / 100	492 ms	1114112 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
// #include "grader.cpp"
using namespace std;

int n, m;

vector<vector<bool>> rv;

vector<int> p2, dX = {-1, 0, 1, 0}, dY = {0, 1, 0, -1};

vector<vector<int>> p1;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C;

    rv.assign(n + 2, vector<bool>(m + 2));
    rv[0][0] = rv[1][0] = rv[0][m + 1] = rv[1][m + 1] = rv[sr][sc] = true;
    for (int i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
    
        rv[sr][sc] = true;
    }

    p2.assign(m + 2, 0);
    p1.assign(3, vector<int>(m + 2));
    for (int i = 1; i <= m; i++) {
        p1[1][i] = p1[1][i - 1] + (!rv[1][i - 1] && rv[1][i]);
        p1[2][i] = p1[2][i - 1] + (!rv[2][i - 1] && rv[2][i]);

        p2[i] = p2[i - 1] + (rv[1][i] && rv[2][i] && !rv[1][i - 1] && !rv[2][i - 1]);
        if (!rv[1][i] && rv[1][i + 1] && rv[2][i]) p2[i]++;
        if (rv[1][i] && !rv[2][i] && rv[2][i + 1]) p2[i]++;
    }
}

int colour(int ar, int ac, int br, int bc) {
    if (ar == br) return p1[ar][bc] - p1[ar][ac] + !rv[ar][bc];

    bool tr1 = (rv[1][bc] && rv[2][bc] && !rv[1][bc - 1] && !rv[2][bc - 1]);
    bool tr2 = (rv[1][ac] && rv[2][ac] && !rv[1][ac - 1] && !rv[2][ac - 1]);
    return p2[bc - 1] - p2[ac - 1] + tr1 - tr2 + (!rv[1][bc] || !rv[2][bc]);
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26