oj.uz

답안 #919271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919271 2024-01-31T13:57:07 Z boris_mihov 무지개나라 (APIO17_rainbow) C++17
0 / 100
 4 ms 8540 KB 
#include "rainbow.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

int n, m;
int vertex[MAXN][MAXN];
int edgesRight[MAXN][MAXN];
int edgesDown[MAXN][MAXN];
int sides[MAXN][MAXN];
bool t[MAXN][MAXN];
int minX = INF;
int maxX;
int minY = INF;
int maxY;

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

    for (int i = 0 ; i < M ; ++i)
    {
        minX = std::min(minX, sr);
        maxX = std::max(maxX, sr);
        minY = std::min(minY, sc);
        maxY = std::max(maxY, sc);
        t[sr][sc] = 1;
        if (S[i] == 'N')
        {
            sr--;
        } else if (S[i] == 'E')
        {
            sc++;
        } else if (S[i] == 'S')
        {
            sr++;
        } else if (S[i] == 'W')
        {
            sc--;
        } else
        {
            assert(false);
        }
    }

    t[sr][sc] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            vertex[i][j] = !t[i][j];
            if (i < n) edgesDown[i][j] = !t[i][j] && !t[i + 1][j];
            if (j < m) edgesRight[i][j] = !t[i][j] && !t[i][j + 1];
            if (i < n && j < m) sides[i][j] = !t[i][j] && !t[i][j + 1] && !t[i + 1][j] && !t[i + 1][j + 1];
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            vertex[i][j] += vertex[i - 1][j] + vertex[i][j - 1] - vertex[i - 1][j - 1];
            edgesRight[i][j] += edgesRight[i - 1][j] + edgesRight[i][j - 1] - edgesRight[i - 1][j - 1];
            edgesDown[i][j] += edgesDown[i - 1][j] + edgesDown[i][j - 1] - edgesDown[i - 1][j - 1];
            sides[i][j] += sides[i - 1][j] + sides[i][j - 1] - sides[i - 1][j - 1];
        }
    }
}

int calc(int prefix[][MAXN], int fromX, int fromY, int toX, int toY)
{
    if (fromX > toX || fromY > toY) return 0;
    return prefix[toX][toY] - prefix[fromX - 1][toY] - prefix[toX][fromY - 1] + prefix[fromX - 1][fromY - 1];
}

int colour(int ar, int ac, int br, int bc) 
{
    int res = 0;
    res += calc(vertex, ar, ac, br, bc);
    res += calc(sides, ar, ac, br - 1, bc - 1);
    if (ar < minX && ac < minY && br > maxX && bc > maxY) // another side
    {
        res++;
    }

    res -= calc(edgesRight, ar, ac, br, bc - 1);
    res -= calc(edgesDown, ar, ac, br - 1, bc);
    return res;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 3 ms 8536 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Incorrect 2 ms 8536 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Incorrect 2 ms 8536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 3 ms 8536 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Incorrect 2 ms 8536 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 3 ms 8536 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Incorrect 2 ms 8536 KB Output isn't correct
8 Halted 0 ms 0 KB -