Submission #249245

#	Time	Username	Problem	Language	Result	Execution time	Memory
249245		SamAnd	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3122 ms	869148 KiB

rainbow

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

    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 (stderr)

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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26