oj.uz

Submission #249254

# Submission time Handle Problem Language Result Execution time Memory
249254 2020-07-14T14:17:33 Z SamAnd Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 557032 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)
{
    if (max(x1, minx) > min(x2, maxx))
        return 0;
    if (max(y1_, miny) > max(y2, maxy))
        return 0;

    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 138 ms 504 KB Output is correct
3 Incorrect 410 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 0 ms 256 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 289 ms 23884 KB Output is correct
3 Correct 235 ms 23884 KB Output is correct
4 Execution timed out 3117 ms 557032 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 138 ms 504 KB Output is correct
3 Incorrect 410 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 138 ms 504 KB Output is correct
3 Incorrect 410 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -