oj.uz

Submission #257293

# Submission time Handle Problem Language Result Execution time Memory
257293 2020-08-04T05:05:06 Z KoD Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 734 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>

#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 19 "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;
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;
}

#ifdef LOCAL

#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;
}

#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 37 ms 384 KB Output is correct
4 Correct 35 ms 504 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 32 ms 384 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 24 ms 384 KB Output is correct
14 Correct 20 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

# 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 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 734 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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 37 ms 384 KB Output is correct
4 Correct 35 ms 504 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 32 ms 384 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 24 ms 384 KB Output is correct
14 Correct 20 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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 37 ms 384 KB Output is correct
4 Correct 35 ms 504 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 32 ms 384 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 24 ms 384 KB Output is correct
14 Correct 20 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 -