oj.uz

답안 #257351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257351 2020-08-04T06:49:15 Z KoD 무지개나라 (APIO17_rainbow) C++17
11 / 100
 517 ms 1048580 KB 
#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;
i32 inside;
 
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;
    }
  }
  {
    std::vector<std::vector<bool>> visited(H, std::vector<bool>(W));
    auto ok = [&](i32 x, i32 y) {
      return !(x < 0 || x >= H || y < 0 || y >= W || 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(0, H)) {
      for (auto j: range(0, W)) {
        if (ok(i, j)) {
          ++res;
          dfs(i, j);
        }
      }
    }
    inside = res - 1;
  }
}
 
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 (V == (br - ar) * (bc - ac)) {
    return 1;
  }
  if (all_inside) {
    return inside + 1;
  }
  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 181 "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, 20);
  i32 C = random_integer(1, 20);
  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:150:28: warning: unused variable 'count' [-Wunused-variable]

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 5 ms 384 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 6 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 517 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 5 ms 384 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 6 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Runtime error 2 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 5 ms 384 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 6 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Runtime error 2 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -