Submission #357732

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
357732	2021-01-24 14:33:25	KoD	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	627 ms	27392 KiB

catdog

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "catdog.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <array>
namespace Solver {
  template <class T>
  using Vec = std::vector<T>;
  constexpr int MAX = 100000;
  struct Monoid {
    static constexpr Monoid ID() { return Monoid { { 0, MAX, MAX, 0 } }; }
    std::array<std::array<long long, 2>, 2> value;
    Monoid operator + (const Monoid &other) const {
      Monoid ret{ { MAX, MAX, MAX, MAX }};
      for (int i: { 0, 1 }) {
        for (int j: { 0, 1 }) {
          for (int k: { 0, 1 }) {
            for (int l: { 0, 1 }) {
              ret.value[i][l] = std::min(ret.value[i][l], value[i][j] + other.value[k][l] + (j ^ k));
            }
          }
        }
      }
      return ret;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62