oj.uz

Submission #249272

# Submission time Handle Problem Language Result Execution time Memory
249272 2020-07-14T14:42:55 Z SamAnd Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 909000 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;

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));
    minx = min(minx, x);
    maxx = max(maxx, x);
    miny = min(miny, y);
    maxy = max(maxy, 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);
    }
}

vector<int> ul[3], ur[3];

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]);
    }

    if (n == 2)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int i = 1; i <= n; ++i)
            {
                if (c.find(m_p(i, j)) == c.end())
                {
                    minx = maxx = i;
                    miny = maxy = j;
                    dfs(i, j, 1, 1, 2, m);
                    ul[0].push_back(miny);
                    ur[0].push_back(maxy);
                }
            }
        }
        for (int i = 1; i <= 2; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (::s.find(m_p(i, j)) == ::s.end())
                {
                    if (j == 1 || ::s.find(m_p(i, j - 1)) != ::s.end())
                    {
                        ul[i].push_back(j);
                    }
                    if (j == m || ::s.find(m_p(i, j + 1)) != ::s.end())
                    {
                        ur[i].push_back(j);
                    }
                }
            }
        }
    }

    /*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);
    }*/
}

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;*/
    /*x1 = max(x1, minx - 2);
    x2 = min(x2, maxx + 2);
    y1_ = max(y1_, miny - 2);
    y2 = min(y2, maxy + 2);*/

    if (n == 2)
    {
        int z;
        if (x1 < x2)
            z = 0;
        else
            z = x1;
        int l = upper_bound(all(ul[z]), y2) - ul[z].begin();
        int r = lower_bound(all(ur[z]), y1_) - ur[z].begin();
        if (l > r)
            return 0;
        return r - l + 1;
    }

    c.clear();

    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:64: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 147 ms 384 KB Output is correct
3 Correct 413 ms 640 KB Output is correct
4 Correct 432 ms 632 KB Output is correct
5 Correct 126 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 325 ms 632 KB Output is correct
12 Correct 271 ms 632 KB Output is correct
13 Correct 214 ms 512 KB Output is correct
14 Correct 122 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Incorrect 0 ms 256 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Execution timed out 3113 ms 909000 KB Time limit exceeded
3 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 147 ms 384 KB Output is correct
3 Correct 413 ms 640 KB Output is correct
4 Correct 432 ms 632 KB Output is correct
5 Correct 126 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 325 ms 632 KB Output is correct
12 Correct 271 ms 632 KB Output is correct
13 Correct 214 ms 512 KB Output is correct
14 Correct 122 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Incorrect 0 ms 256 KB Output isn't correct
17 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 147 ms 384 KB Output is correct
3 Correct 413 ms 640 KB Output is correct
4 Correct 432 ms 632 KB Output is correct
5 Correct 126 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 325 ms 632 KB Output is correct
12 Correct 271 ms 632 KB Output is correct
13 Correct 214 ms 512 KB Output is correct
14 Correct 122 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Incorrect 0 ms 256 KB Output isn't correct
17 Halted 0 ms 0 KB -