oj.uz

Submission #249368

# Submission time Handle Problem Language Result Execution time Memory
249368 2020-07-14T17:07:12 Z SamAnd Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 3000 ms 71316 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> > t;
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;
    if (t.find(m_p(x, y)) == t.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]);
        for (int j = 0; j < 4; ++j)
        {
            t.insert(m_p(v[i].fi + xx[j], v[i].se + yy[j]));
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        t.insert(m_p(i, 1));
        t.insert(m_p(i, m));
    }
    for (int j = 1; j <= m; ++j)
    {
        t.insert(m_p(1, j));
        t.insert(m_p(n, j));
    }

    if (n == 2)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int i = 1; i <= n; ++i)
            {
                if (::s.find(m_p(i, j)) != ::s.end())
                    continue;
                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 <= m; ++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 r = upper_bound(all(ul[z]), y2) - ul[z].begin() - 1;
        int l = 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:67: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 Incorrect 23 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 867 ms 67564 KB Output is correct
4 Correct 746 ms 62824 KB Output is correct
5 Correct 742 ms 64360 KB Output is correct
6 Correct 838 ms 71172 KB Output is correct
7 Correct 969 ms 71020 KB Output is correct
8 Correct 638 ms 57580 KB Output is correct
9 Correct 835 ms 62700 KB Output is correct
10 Correct 761 ms 64312 KB Output is correct
11 Correct 840 ms 71276 KB Output is correct
12 Correct 867 ms 62064 KB Output is correct
13 Correct 718 ms 62700 KB Output is correct
14 Correct 788 ms 64488 KB Output is correct
15 Correct 845 ms 71316 KB Output is correct
16 Correct 889 ms 66100 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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