제출 #257364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257364		KoD	무지개나라 (APIO17_rainbow)	C++17	35 / 100	3085 ms	49272 KiB

rainbow

#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>
#include <map>

#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 21 "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, 1, 1, -1, -1 };
constexpr i32 dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };

i32 H, W;
i32 query_counter;
i32 query_all;
std::set<std::pair<i32, i32>> nov, noe_h, noe_w, noc;

void disable(i32 x, i32 y) {
  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);
}

bool adjacent(i32 x, i32 y) {
  if (nov.find(std::make_pair(x, y)) != nov.end()) {
    return false;
  }
  for (auto k: range(0, 8)) {
    if (nov.find(std::make_pair(x + dx[k], y + dy[k])) != nov.end()) {
      return true;
    }
  }
  return false;
}

void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
  H = R, W = C;
  {
    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);
    }
  }
  {
    std::set<std::pair<i32, i32>> visited;
    auto dfs = fix_point([&](auto dfs, i32 x, i32 y) -> void {
      if (visited.find(std::make_pair(x, y)) != visited.end()) {
        return;
      }
      visited.insert(std::make_pair(x, y));
      for (auto k: range(0, 4)) {
        i32 nx = x + dx[k], ny = y + dy[k];
        if (adjacent(nx, ny)) {
          dfs(nx, ny);
        }
      }
    });
    query_all = 0;
    for (auto [x, y]: nov) {
      for (auto k: range(0, 4)) {
        i32 nx = x + dx[k], ny = y + dy[k];
        if (adjacent(nx, ny) && visited.find(std::make_pair(nx, ny)) == visited.end()) {
          ++query_all;
          dfs(nx, ny);
        }
      }
    }
  }
}

i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
  ++query_counter;
  --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);
  bool all_inside = true;
  bool exists = false;
  for (auto [x, y]: nov) {
    if (ar <= x && x <= br && ac <= y && y <= bc) {
      if (!(ar < x && x < br && ac < y && y < bc)) {
        all_inside = false;
      }
      exists = true;
      --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;
    }
  }
  if (!exists) {
    return 1;
  }
  if (all_inside) {
    return query_all;
  }
  return C - E + V;
}

#line 1 "/Users/kodamankod/Desktop/Programming/Library/other/random_number.cpp"

#include <cstdint>
#include <random>
#include <chrono>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/random_number.cpp"

uint64_t engine() {
  const auto rotate = [](const uint64_t x, const size_t k) {
    return (x << k) | (x >> (64 - k));
  };
  static auto array = [] {
    uint64_t seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::array<uint64_t, 4> res{};
    for (size_t index = 0; index < 4; index++) {
      uint64_t value = (seed += 0x9e3779b97f4a7c15);
      value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9;
      value = (value ^ (value >> 27)) * 0x94d049bb133111eb;
      res[index] = value ^ (value >> 31);
    }
    return res;
  }();
  const uint64_t result = rotate(array[1] * 5, 7) * 9;
  const uint64_t old_value = array[1] << 17;
  array[2] ^= array[0];
  array[3] ^= array[1];
  array[1] ^= array[2];
  array[0] ^= array[3];
  array[2] ^= old_value;
  array[3] = rotate(array[3], 45);
  return result;
}

template <class Integer>
Integer random_integer(Integer lower, Integer upper) {
  static std::default_random_engine gen(engine());
  return std::uniform_int_distribution<Integer>(lower, upper)(gen);
}

template <class Real>
Real random_real(Real lower, Real upper) {
  static std::default_random_engine gen(engine());
  return std::uniform_real_distribution<Real>(lower, upper)(gen);
}

/** 
 * @title Random Number
 */
#line 145 "main.cpp"
#ifdef LOCAL

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, 5);
  i32 C = random_integer(1, 5);
  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)) {
          bool x = kod::river[i][j];
          if (x) {
            std::cout << "\033[31m1\033[0m";
          }
          else {
            std::cout << "0";
          }
        }
        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

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26