oj.uz

Submission #249251

# Submission time Handle Problem Language Result Execution time Memory
249251 2020-07-14T14:14:47 Z SamAnd Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 560312 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 200005;
const int xx[4] = {-1, 1, 0, 0};
const int yy[4] = {0, 0, -1, 1};
const char cc[4] = {'N', 'S', 'W', 'E'};

int n, m;

set<pair<int, int> > s;

int minx, maxx, miny, maxy;

void init(int R, int C, int sx, int sy, int ss, char *s)
{
    n = R;
    m = C;
    vector<pair<int, int> > v;
    v.push_back(m_p(sx, sy));
    for (int i = 0; i < ss; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (cc[j] == s[i])
            {
                v.push_back(m_p(v.back().fi + xx[j], v.back().se + yy[j]));
            }
        }
    }
    for (int i = 0; i < v.size(); ++i)
    {
        ::s.insert(v[i]);
    }

    minx = maxx = sx;
    miny = maxy = sy;
    for (int i = 0; i < v.size(); ++i)
    {
        minx = min(minx, v[i].fi);
        maxx = max(maxx, v[i].fi);
        miny = min(miny, v[i].se);
        maxy = max(maxy, v[i].se);
    }
}

set<pair<int, int> > c;

void dfs(int x, int y, int x1, int y1_, int x2, int y2)
{
    if (!(x1 <= x && x <= x2))
        return;
    if (!(y1_ <= y && y <= y2))
        return;
    if (s.find(m_p(x, y)) != s.end())
        return;
    if (c.find(m_p(x, y)) != c.end())
        return;
    c.insert(m_p(x, y));
    for (int i = 0; i < 4; ++i)
    {
        int hx = x + xx[i];
        int hy = y + yy[i];
        dfs(hx, hy, x1, y1_, x2, y2);
    }
}

int colour(int x1, int y1_, int x2, int y2)
{
    c.clear();

    x1 = max(x1, min(minx - 2, x2));
    x2 = min(x2, max(maxx + 2, x1));
    y1_ = max(y1_, min(miny - 2, y2));
    y2 = min(y2, max(maxy + 2, y1_));

    int ans = 0;
    for (int x = x1; x <= x2; ++x)
    {
        for (int y = y1_; y <= y2; ++y)
        {
            if (s.find(m_p(x, y)) != s.end())
                continue;
            if (c.find(m_p(x, y)) == c.end())
            {
                ++ans;
                dfs(x, y, x1, y1_, x2, y2);
            }
        }
    }
    return ans;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
rainbow.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 384 KB Output is correct
2 Correct 137 ms 512 KB Output is correct
3 Correct 407 ms 640 KB Output is correct
4 Correct 434 ms 668 KB Output is correct
5 Correct 127 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 274 ms 568 KB Output is correct
12 Correct 179 ms 504 KB Output is correct
13 Correct 203 ms 592 KB Output is correct
14 Correct 116 ms 512 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Execution timed out 3082 ms 7492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 282 ms 23884 KB Output is correct
3 Correct 239 ms 24012 KB Output is correct
4 Execution timed out 3079 ms 560312 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 384 KB Output is correct
2 Correct 137 ms 512 KB Output is correct
3 Correct 407 ms 640 KB Output is correct
4 Correct 434 ms 668 KB Output is correct
5 Correct 127 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 274 ms 568 KB Output is correct
12 Correct 179 ms 504 KB Output is correct
13 Correct 203 ms 592 KB Output is correct
14 Correct 116 ms 512 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Execution timed out 3062 ms 33856 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 384 KB Output is correct
2 Correct 137 ms 512 KB Output is correct
3 Correct 407 ms 640 KB Output is correct
4 Correct 434 ms 668 KB Output is correct
5 Correct 127 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 274 ms 568 KB Output is correct
12 Correct 179 ms 504 KB Output is correct
13 Correct 203 ms 592 KB Output is correct
14 Correct 116 ms 512 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Execution timed out 3062 ms 33856 KB Time limit exceeded
19 Halted 0 ms 0 KB -