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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;

template <typename T>
using Grid = array<vector<T>, 2>;

struct TestCase
{
  size_t N, K;
  Grid<size_t> rows;
};

TestCase read_test_case();
void solve_test_case(const TestCase&);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve_test_case(read_test_case());
}

TestCase read_test_case()
{
  TestCase tc;
  cin >> tc.N >> tc.K;
  for (size_t i = 0; i < 2; i++)
  {
    tc.rows[i].resize(tc.N);
    for (auto& v : tc.rows[i])
    {
      cin >> v;
      v--;
    }
  }
  return tc;
}

void solve_small_n(const TestCase& tc);

void solve_test_case(const TestCase& tc) { solve_small_n(tc); }

size_t count_areas(const TestCase& tc, size_t low, size_t high);

void solve_small_n(const TestCase& tc)
{
  vector<size_t> cnt(tc.K + 1);

  for (size_t high = 0; high < tc.N * 2; high++)
    for (size_t low = 0; low <= high; low++)
    {
      size_t areas = count_areas(tc, low, high);
      if (areas <= tc.K) cnt[areas]++;
    }

  for (size_t i = 1; i <= tc.K; i++) cout << cnt[i] << " ";
  cout << "\n";
}

void visit_dfs(
    const TestCase& tc, Grid<bool>& visited, size_t low, size_t high, size_t i,
    size_t j);

size_t count_areas(const TestCase& tc, size_t low, size_t high)
{
  size_t cnt = 0;

  Grid<bool> visited;
  visited[0].resize(tc.N);
  visited[1].resize(tc.N);

  for (size_t i = 0; i < 2; i++)
    for (size_t j = 0; j < tc.N; j++)
      if (!visited[i][j] && low <= tc.rows[i][j] && tc.rows[i][j] <= high)
      {
        visit_dfs(tc, visited, low, high, i, j);
        cnt++;
      }

  return cnt;
}

void visit_dfs(
    const TestCase& tc, Grid<bool>& visited, size_t low, size_t high, size_t i,
    size_t j)
{
  if (visited[i][j]) return;
  if (tc.rows[i][j] < low || tc.rows[i][j] > high) return;
  visited[i][j] = true;

  visit_dfs(tc, visited, low, high, (i + 1) % 2, j);
  visit_dfs(tc, visited, low, high, i, (j + 1) % tc.N);
  visit_dfs(tc, visited, low, high, i, (j + tc.N - 1) % tc.N);
}