#line 1 "main.cpp"
/**
* @title Template
*/
#line 1 "rainbow.h"
#ifdef LOCAL
#ifndef __RAINBOW_H
#define __RAINBOW_H
#include <cstdint>
void init(int32_t R, int32_t C, int32_t sr, int32_t sc, int32_t M, char * S);
int32_t colour(int32_t ar, int32_t ac, int32_t br, int32_t bc);
#endif // __RAINBOW_H
#endif
#line 7 "main.cpp"
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <set>
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"
template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
class range {
public:
class iterator {
private:
int64_t M_position;
public:
constexpr iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { ++M_position; }
constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { --M_position; }
constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
constexpr iterator begin() const noexcept { return M_first; }
constexpr iterator end() const noexcept { return M_last; }
constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
template <class T>
class rev_impl {
public:
using iterator = typename std::decay<T>::type::reverse_iterator;
private:
const iterator M_begin;
const iterator M_end;
public:
constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
constexpr iterator begin() const noexcept { return M_begin; }
constexpr iterator end() const noexcept { return M_end; }
};
template <class T>
constexpr decltype(auto) rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
template <class Func>
struct fix_point_impl: private Func {
explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }
template <class... Args>
constexpr decltype(auto) operator () (Args &&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
return fix_point_impl<Func>(std::forward<Func>(func));
}
/**
* @title Lambda Recursion
*/
#line 20 "main.cpp"
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
constexpr i32 dx[] = { 0, 1, 0, -1 };
constexpr i32 dy[] = { 1, 0, -1, 0 };
/*
i32 H, W;
i32 query_counter;
// std::vector<std::vector<bool>> river;
std::set<std::pair<i32, i32>> nov, noe_h, noe_w, noc;
void disable(i32 x, i32 y) {
// river[x][y] = true;
nov.emplace(x, y);
noe_h.emplace(x, y);
noe_h.emplace(x - 1, y);
noe_w.emplace(x, y);
noe_w.emplace(x, y - 1);
noc.emplace(x, y);
noc.emplace(x - 1, y);
noc.emplace(x, y - 1);
noc.emplace(x - 1, y - 1);
}
void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
H = R, W = C;
// river = std::vector<std::vector<bool>>(H, std::vector<bool>(W));
{
i32 x = sr - 1, y = sc - 1;
disable(x, y);
for (auto i: range(0, M)) {
char c = S[i];
if (c == 'N') --x;
if (c == 'E') ++y;
if (c == 'W') --y;
if (c == 'S') ++x;
disable(x, y);
}
}
}
i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
++query_counter;
// assert(query_counter <= 10);
--ar; --ac; --br; --bc;
i64 V = (i64) (br - ar + 1) * (bc - ac + 1);
i64 E = (i64) (br - ar) * (bc - ac + 1) + (i64) (bc - ac) * (br - ar + 1);
i64 C = (i64) (br - ar) * (bc - ac);
for (auto [x, y]: nov) {
if (ar <= x && x <= br && ac <= y && y <= bc) {
--V;
}
}
for (auto [x, y]: noe_h) {
if (ar <= x && x < br && ac <= y && y <= bc) {
--E;
}
}
for (auto [x, y]: noe_w) {
if (ar <= x && x <= br && ac <= y && y < bc) {
--E;
}
}
for (auto [x, y]: noc) {
if (ar <= x && x < br && ac <= y && y < bc) {
--C;
}
}
return C - E + V;
}
*/
i32 H, W;
std::vector<std::vector<bool>> river;
void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
H = R, W = C;
river = std::vector<std::vector<bool>>(H, std::vector<bool>(W));
assert(R <= 50 && C <= 50);
{
i32 x = sr - 1, y = sc - 1;
river[x][y] = true;
for (auto i: range(0, M)) {
char c = S[i];
if (c == 'N') --x;
if (c == 'E') ++y;
if (c == 'W') --y;
if (c == 'S') ++x;
river[x][y] = true;
}
}
}
i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
--ar; --ac;
auto ok = [&](i32 x, i32 y) {
return !(x < ar || x >= br || y < ac || y >= bc || river[x][y]);
};
i32 V = 0, E = 0, C = 0, count = 0;
bool all_inside = true;
for (auto i: range(ar, br)) {
for (auto j: range(ac, bc)) {
if (river[i][j] && !(ar < i && i + 1 < br && ac < j && j + 1 < bc)) {
all_inside = false;
}
if (ok(i, j)) {
++V;
}
if (ok(i, j) && ok(i, j + 1)) {
++E;
}
if (ok(i, j) && ok(i + 1, j)) {
++E;
}
if (ok(i, j) && ok(i, j + 1) && ok(i + 1, j) && ok(i + 1, j + 1)) {
++C;
}
}
}
if (all_inside) {
return 1;
}
return C - E + V;
}
#ifdef LOCAL
// #include "/Users/kodamankod/Desktop/Programming/Library/other/random_number.cpp"
namespace kod {
i32 H, W;
std::vector<std::vector<bool>> river;
void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
H = R, W = C;
river = std::vector<std::vector<bool>>(H, std::vector<bool>(W));
assert(R <= 50 && C <= 50);
{
i32 x = sr - 1, y = sc - 1;
river[x][y] = true;
for (auto i: range(0, M)) {
char c = S[i];
if (c == 'N') --x;
if (c == 'E') ++y;
if (c == 'W') --y;
if (c == 'S') ++x;
river[x][y] = true;
}
}
}
i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
--ar; --ac;
std::vector<std::vector<bool>> visited(H, std::vector<bool>(W));
auto ok = [&](i32 x, i32 y) {
return !(x < ar || x >= br || y < ac || y >= bc || river[x][y] || visited[x][y]);
};
auto dfs = fix_point([&](auto dfs, i32 x, i32 y) -> void {
if (!ok(x, y)) return;
visited[x][y] = true;
for (auto k: range(0, 4)) {
dfs(x + dx[k], y + dy[k]);
}
});
i32 res = 0;
for (auto i: range(ar, br)) {
for (auto j: range(ac, bc)) {
if (ok(i, j)) {
++res;
dfs(i, j);
}
}
}
return res;
}
};
#include <stdio.h>
/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}
*/
int main() {
while (true) {
i32 R = random_integer(1, 10);
i32 C = random_integer(1, 10);
i32 M = random_integer(0, R * C);
i32 sr = random_integer(1, R);
i32 sc = random_integer(1, C);
i32 Q = random_integer(0, 100);
char *S = new char[M + 1];
{
i32 x = sr, y = sc;
for (auto i: range(0, M)) {
while (true) {
i32 k = random_integer(0, 3);
i32 nx = x + dx[k], ny = y + dy[k];
if (1 <= nx && nx <= R && 1 <= ny && ny <= C) {
S[i] = "ESWN"[k];
x = nx;
y = ny;
break;
}
}
}
}
init(R, C, sr, sc, M, S);
kod::init(R, C, sr, sc, M, S);
while (Q--) {
i32 ar = random_integer(1, R), ac = random_integer(1, C);
i32 br = random_integer(ar, R), bc = random_integer(ac, C);
if (colour(ar, ac, br, bc) != kod::colour(ar, ac, br, bc)) {
for (auto i: range(0, R)) {
for (auto j: range(0, C)) {
std::cout << kod::river[i][j];
}
std::cout << '\n';
}
std::cout << ar << ' ' << ac << ' ' << br << ' ' << bc << '\n';
std::cout << colour(ar, ac, br, bc) << ' '<< kod::colour(ar, ac, br, bc) << '\n';
return 0;
}
}
}
}
#endif
Compilation message
main.cpp: In function 'i32 colour(i32, i32, i32, i32)':
main.cpp:126:28: warning: unused variable 'count' [-Wunused-variable]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
540 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
