Submission #685355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
685355	2023-01-24T06:46:42 Z	lunchbox1	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	378 ms	262144 KB

dango_maker

// #include <algorithm>
// #include <array>
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <numeric>
#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

#define assert(...) 0

// https://judge.yosupo.jp/submission/110301

struct BipartiteGraph{ // https://judge.yosupo.jp/submission/59969
  // Max matching in O(E root(V)) --> considerably fast, runs under 100ms for E, V <= 2e5 on library checker
private:
    int n;
    int Lpart, Rpart;
    int matching_num;
    // std::vector<std::vector<int>> G;
    vector<array<int, 2>> raw_edges;
    vector<int> num_starts, final_edges;

public:
    std::vector<int> match;

    BipartiteGraph(int a, int b, int p = 0): Lpart(a), Rpart(b), n(a + b), matching_num(-1), num_starts(a + b + 1, 0), match(n, -1) {
      raw_edges.reserve(p);
    }
    BipartiteGraph(int a, int b, const vector<array<int, 2>>& Edges): Lpart(a), Rpart(b), n(a + b), matching_num(-1), raw_edges(Edges), num_starts(a + b + 1, 0), match(n, -1) {}

    inline void addEdge(int u, int v){ raw_edges.push_back({u, v});}

    inline void build() {
      for(const auto& [u, v]: raw_edges) {
        ++num_starts[u + 1];
        ++num_starts[v + Lpart + 1];
      }
      for(int i = 1; i <= n; ++i) num_starts[i] += num_starts[i - 1];
      final_edges.resize(num_starts[n]);
      vector<int> start(num_starts.begin(), num_starts.begin() + n);

      for(const auto& [u, v]: raw_edges){
        final_edges[start[u]++] = v + Lpart;
        final_edges[start[v + Lpart]++] = u;
      }

    }
    int maxMatching(){
      if (final_edges.size() != raw_edges.size()) build();

        int res = 0; bool update = true;
        std::vector<int> pre(Lpart, -1), root(Lpart, -1);
        while(update){
            update = false; std::queue<int> que;
            for(int i = 0; i < Lpart; i++){
                if(!~match[i]){
                    root[i] = i; que.push(i);
                }
            }
            while(que.size()){
                int v = que.front(); que.pop();
                if(~match[root[v]]) continue;
                for(int cur = num_starts[v]; cur < num_starts[v + 1]; ++cur){
                  int nv = final_edges[cur];
                    if(!~match[nv]){
                        while(~nv){
                            match[nv] = v; std::swap(match[v], nv); v = pre[v];
                        }
                        update = true; ++res;
                        break;
                    }
                    nv = match[nv];
                    if(~pre[nv]) continue;
                    pre[nv] = v, root[nv] = root[v];
                    que.push(nv);
                }
            }
            if(update){
                std::fill(pre.begin(), pre.end(), -1);
                std::fill(root.begin(), root.end(), -1);
            }
        }
        return matching_num = res;
    }

    std::vector<std::array<int, 2>> maxMatchingEdges() {
      if (matching_num == -1)
        maxMatching();
      std::vector<std::array<int, 2>> ans; ans.reserve(matching_num);

      for(int i = 0; i < Lpart; ++i){
        if (match[i] != -1)
          ans.push_back({i, match[i] - Lpart});
      }
      return ans;
    }


    inline int pair(int u) const {return match[u];}

    std::vector<std::array<int, 2>> minimumEdgeCover(){ // Minimum edges to cover each vertex atleast once.
        if (matching_num == -1)
          maxMatching();
        int idx = 0;
        std::vector<std::array<int, 2>> res(n - matching_num);
        for(int i = 0; i < Lpart; i++){
            if(match[i] != -1) res[idx++] = {i, match[i]};
            else res[idx++] = {i, final_edges[num_starts[i + 1] - 1]};
        }
        assert(n - matching_num == idx);
        return res;
    }

    std::pair<std::vector<int>, std::vector<int>> minimumVertexCover(){
        if (matching_num == -1)
          maxMatching();
        std::vector<bool> reachable(n);
        for(int i = 0; i < Lpart; i++){
            if(match[i] != -1) continue;
            std::queue<int> que;
            que.push(i);
            while(que.size()){
                int v = que.front(); que.pop();
                reachable[v] = true;
                for(int cur = num_starts[v]; cur < num_starts[v + 1]; ++cur){
                  const int nv = final_edges[cur];
                    if(reachable[nv]) continue;
                    if(v >= Lpart && match[v] == nv){
                        reachable[nv] = true;
                        que.push(nv);
                    }
                    if(v < Lpart && match[v] != nv){
                        reachable[nv] = true;
                        que.push(nv);
                    }
                }
            }
        } 
        std::vector<int> left, right;
        for(int i = 0; i < n; i++){
            if(i < Lpart && !reachable[i]) left.emplace_back(i);
            if(i >= Lpart && reachable[i]) right.emplace_back(i);
        }  
        return std::make_pair(left, right);
    }   

    std::pair<std::vector<int>, std::vector<int>> maxIndependentSet(){
        if (matching_num == -1)
          maxMatching();

        std::vector<int> left, right;
        auto p = minimumVertexCover();
        std::vector<bool> complement(n, false);
        for(const int &v : p.first) complement[v] = true;
        for(const int &v : p.second) complement[v] = true;
        for(int i = 0; i < n; i++){
            if(complement[i]) continue;
            if(i < Lpart) right.emplace_back(i);
            else left.emplace_back(i);
        }
        return std::make_pair(left, right);
    }
};




struct BipartiteEdgeColoring {
  struct UnionFind {
    vector<int> UF; UnionFind(int N) : UF(N, -1) {}
    inline int find(int v) { return UF[v] < 0 ? v : UF[v] = find(UF[v]); }
    inline void join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) return;
    if (UF[v] > UF[w]) swap(v, w);
    UF[v] += UF[w]; UF[w] = v; return;}
  };

  struct Pair {
    int s, v; Pair(int s, int v) : s(s), v(v) {}
    bool operator < (const Pair &o) const { return s > o.s; }
  };
  int makeDRegular(int &V, vector<pair<int, int>> &edges, int &L) { // O(V log V + E), adds atmost E + D new edges
    vector<int> deg(V, 0); 
    for (auto &&e : edges) {
      deg[e.first]++; deg[e.second]++;
    }
    int D = *max_element(deg.begin(), deg.end()); UnionFind uf(V);
    vector<int> cnt(2, 0);
    int R = V - L;
    for (int s = 0; s < 2; s++) {
      std::priority_queue<Pair> PQ;
        for(int v = s * L; v < L + s * R; ++v) {
          PQ.push({deg[v], v});
        }
    cnt[s] = PQ.size();
    while (int(PQ.size()) >= 2) {
      Pair a = PQ.top(); PQ.pop(); Pair b = PQ.top(); PQ.pop();
      if (a.s + b.s <= D) { uf.join(a.v, b.v); PQ.emplace(a.s + b.s, a.v); --cnt[s];}
      else break;
    }
    }
    vector<int> id(V, -1); 
    if (cnt[0] >= cnt[1]) {
      int curId = 0;
      for(int v = 0;  v < V; ++v)
        if (uf.find(v) == v)
          id[v] = curId++;
    }
    else{
      int curId = 0;
      for(int v = V - 1;  v >= 0; --v)
        if (uf.find(v) == v)
          id[v] = curId++;
      for(auto &&e: edges){
        swap(e.first, e.second);
      }
      swap(cnt[0], cnt[1]);
    }
    assert (cnt[0] >= cnt[1]);
    deg.assign(V = cnt[0] * 2, 0); edges.reserve(V * D / 2);

    for (auto &&e : edges) {
      deg[e.first = id[uf.find(e.first)]]++;
      deg[e.second = id[uf.find(e.second)]]++;
      assert (e.first < e.second);
    }

    for(int v = 0, w = cnt[0]; v < cnt[0]; ++v) {
      while (deg[v] < D){
        while (w < V && deg[w] == D) ++w;
        int x = min(D - deg[w], D - deg[v]);
        for(int k = 0; k < x; ++k){
          edges.emplace_back(v, w);
        }
        deg[v] += x;
        deg[w] += x;
      }
    }
    L = cnt[0];
    return D;
  }
  vector<int> eulerianCircuit(
      int V, const vector<pair<int, int>> &edges, const vector<int> &inds) {
    vector<vector<pair<int, int>>> G(V); vector<int> circuit;
    for (int i = 0; i < int(inds.size()); i++) {
      int v, w; tie(v, w) = edges[inds[i]];
      G[v].emplace_back(w, i); G[w].emplace_back(v, i);
    }
    vector<bool> vis1(V, false), vis2(inds.size(), false);
    vector<pair<int, int>> stk; for (int s = 0; s < V; s++) if (!vis1[s]) {
      stk.clear(); stk.emplace_back(s, -1); while (!stk.empty()) {
        int v, w, e; tie(v, e) = stk.back(); vis1[v] = true;
        if (G[v].empty()) { circuit.emplace_back(e); stk.pop_back(); }
        else {
          tie(w, e) = G[v].back(); G[v].pop_back();
          if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
        }
      }
      circuit.pop_back();
    }
    for (auto &&e : circuit) e = inds[e];
    return circuit;
  }
  vector<int> color;

  // static vector<int> maxMatchDRegular(int V, vector<pair<int, int>> edges, int D, int K) {
  //  const int E = edges.size();
  //  const int L = (V >> 1);
  //  assert (E == ((V * 1LL * D) / 2) && K <= D && (L << 1) == V);
  //  vector<int> color(E, -1);

  //  vector<vector<int>> G(V);

  //  vector<int> xv(E);
  //  for(int i = 0; i < E; ++i) {
  //    int u, v; tie(u, v) = edges[i];
  //    G[u].push_back(i);
  //    xv[i] = u ^ v;
  //  }

  //  vector<int> match(V, -1);
  //  vector<int> path;

  //  function<bool(int, int)> augment = [&] (int u, int b) {
  //    if (u > L) {
  //      if (match[u] == -1){
  //        return true;
  //      }
  //      u = edges[match[u]].second;
  //      path.push_back(match[u]);

  //      int k = G
  //    }
  //    else{
  //      int v = G[u].size();
  //      int x = random_long(0, v - 1);
  //      path.push_back()
  //    }

  //  };

  //  for(int i = 0; i < K; ++i) {

  //  }
  // }

  BipartiteEdgeColoring(int L, int R, vector<pair<int, int>> edges) // O(E sqrt V log (D))
      : color(edges.size(), -1) {
     int V = L + R;
    for (auto &&e : edges) {
      assert(e.first < L && e.second < R);
      e.second += L;
    }

    int D = makeDRegular(V, edges, L), curCol = 0;

    for(auto &&e: edges){
      assert (e.first < L && e.second >= L);
    }
    R = L;
    function<void(int, const vector<int> &)> rec = [&] ( 
        int d, const vector<int> &inds) {
      if (d == 0) return;
      else if (d == 1) {
        for (int e : inds) if (e < int(color.size())) color[e] = curCol;
        curCol++;
      } else if (d % 2 == 0) {
        vector<int> circuit = eulerianCircuit(V, edges, inds), half1, half2;
        half1.reserve(circuit.size() / 2); half2.reserve(circuit.size() / 2);
        for (int i = 0; i < int(circuit.size()); i += 2) {
          half1.push_back(circuit[i]); half2.push_back(circuit[i + 1]);
        }
        rec(d / 2, half1); rec(d / 2, half2);
      } else {


        vector<vector<int>> G(V); 

        BipartiteGraph mm(L, L);

        for (int e : inds) {
          int v, w; tie(v, w) = edges[e]; 
          mm.addEdge(v, w - L);
        }
        mm.maxMatching();
        vector<int> unmatched;
        for (int e : inds) {
          int v, w; tie(v, w) = edges[e]; 
          if (mm.match[v] == w) {
            mm.match[v] = -1; 
            mm.match[w] = -1;
            if (e < int(color.size())) color[e] = curCol;
          } else unmatched.push_back(e);
        }
        curCol++; rec(d - 1, unmatched);
      }
    };
    vector<int> inds(edges.size()); iota(inds.begin(), inds.end(), 0);
    rec(D, inds);
  }
};

int n, m;
string s[N];

bool t1(int i, int j) {
  return i > 0 && i < n - 1 && s[i - 1][j] == 'R' && s[i][j] == 'G' && s[i + 1][j] == 'W';
}

bool t2(int i, int j) {
  return j > 0 && j < m - 1 && s[i][j - 1] == 'R' && s[i][j] == 'G' && s[i][j + 1] == 'W';
}

int iu[N][N], iv[N][N], u = 0, v = 0;
vector<pair<int, int>> edge;



void link_(int i1, int j1, int i2, int j2) {
  if (i1 < 0 || i1 >= n || i2 < 0 || i2 >= n || j1 < 0 || j1 >= m || j2 < 0 || j2 >= m)
    return;
  if (iu[i1][j1] != -1 && iv[i2][j2] != -1) {
    // cout << i1 << ' ' << j1 << " -> " << i2 << ' ' << j2 << '\n';
    edge.push_back({iu[i1][j1], iv[i2][j2]});
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> s[i];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      iu[i][j] = t1(i, j) ? u++ : -1;
      iv[i][j] = t2(i, j) ? v++ : -1;
    }
  // dinic::build(u + v + 2);
  // int s = u + v, t = s + 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      if (iu[i][j] != -1) {
        // cout << "U " << i << ' ' << j << '\n';
        // dinic::link(s, iu[i][j], 1);
        // link_(i, j, i - 1, j + 1);
        // link_(i, j, i + 1, j - 1);
      }
      if (iv[i][j] != -1) {
        // cout << "V " << i << ' ' << j << '\n';
        // dinic::link(u + iv[i][j], t, 1);
        link_(i + 1, j - 1, i, j);
        link_(i - 1, j + 1, i, j);
      }
      link_(i, j, i, j);
    }
  BipartiteGraph g(u, v, edge.size());
  for (auto [u, v] : edge)
    g.addEdge(u, v);
  // HopcroftKarp hk(u, v, edge);
  cout << u + v - g.maxMatchingEdges().size() << '\n';
  return 0;
}

Compilation message

dango_maker.cpp:12: warning: "assert" redefined
   12 | #define assert(...) 0
      | 
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dango_maker.cpp:7:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)       \
      | 
dango_maker.cpp: In constructor 'BipartiteGraph::BipartiteGraph(int, int, int)':
dango_maker.cpp:20:16: warning: 'BipartiteGraph::Rpart' will be initialized after [-Wreorder]
   20 |     int Lpart, Rpart;
      |                ^~~~~
dango_maker.cpp:19:9: warning:   'int BipartiteGraph::n' [-Wreorder]
   19 |     int n;
      |         ^
dango_maker.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     BipartiteGraph(int a, int b, int p = 0): Lpart(a), Rpart(b), n(a + b), matching_num(-1), num_starts(a + b + 1, 0), match(n, -1) {
      |     ^~~~~~~~~~~~~~
dango_maker.cpp: In constructor 'BipartiteGraph::BipartiteGraph(int, int, const std::vector<std::array<int, 2> >&)':
dango_maker.cpp:20:16: warning: 'BipartiteGraph::Rpart' will be initialized after [-Wreorder]
   20 |     int Lpart, Rpart;
      |                ^~~~~
dango_maker.cpp:19:9: warning:   'int BipartiteGraph::n' [-Wreorder]
   19 |     int n;
      |         ^
dango_maker.cpp:32:5: warning:   when initialized here [-Wreorder]
   32 |     BipartiteGraph(int a, int b, const vector<array<int, 2>>& Edges): Lpart(a), Rpart(b), n(a + b), matching_num(-1), raw_edges(Edges), num_starts(a + b + 1, 0), match(n, -1) {}
      |     ^~~~~~~~~~~~~~
dango_maker.cpp: In member function 'std::vector<std::array<int, 2> > BipartiteGraph::minimumEdgeCover()':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:113:9: note: in expansion of macro 'assert'
  113 |         assert(n - matching_num == idx);
      |         ^~~~~~
dango_maker.cpp: In member function 'int BipartiteEdgeColoring::makeDRegular(int&, std::vector<std::pair<int, int> >&, int&)':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:222:5: note: in expansion of macro 'assert'
  222 |     assert (cnt[0] >= cnt[1]);
      |     ^~~~~~
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:228:7: note: in expansion of macro 'assert'
  228 |       assert (e.first < e.second);
      |       ^~~~~~
dango_maker.cpp: In constructor 'BipartiteEdgeColoring::BipartiteEdgeColoring(int, int, std::vector<std::pair<int, int> >)':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:314:7: note: in expansion of macro 'assert'
  314 |       assert(e.first < L && e.second < R);
      |       ^~~~~~
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:321:7: note: in expansion of macro 'assert'
  321 |       assert (e.first < L && e.second >= L);
      |       ^~~~~~
dango_maker.cpp:320:16: warning: unused variable 'e' [-Wunused-variable]
  320 |     for(auto &&e: edges){
      |                ^

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	428 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	424 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	428 KB	Output is correct
14	Correct	0 ms	428 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	428 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	424 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	428 KB	Output is correct
14	Correct	0 ms	428 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	420 KB	Output is correct
23	Correct	1 ms	420 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	428 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	420 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	1 ms	424 KB	Output is correct
34	Correct	0 ms	468 KB	Output is correct
35	Correct	1 ms	424 KB	Output is correct
36	Correct	1 ms	468 KB	Output is correct
37	Correct	1 ms	468 KB	Output is correct
38	Correct	1 ms	468 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct
40	Correct	1 ms	424 KB	Output is correct
41	Correct	1 ms	468 KB	Output is correct
42	Correct	0 ms	468 KB	Output is correct
43	Correct	1 ms	468 KB	Output is correct
44	Correct	1 ms	468 KB	Output is correct
45	Correct	1 ms	468 KB	Output is correct
46	Correct	1 ms	468 KB	Output is correct
47	Correct	1 ms	468 KB	Output is correct
48	Correct	1 ms	468 KB	Output is correct
49	Correct	1 ms	468 KB	Output is correct
50	Correct	1 ms	468 KB	Output is correct
51	Correct	1 ms	420 KB	Output is correct
52	Correct	1 ms	468 KB	Output is correct
53	Correct	1 ms	468 KB	Output is correct

Subtask #3

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	428 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	424 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	428 KB	Output is correct
14	Correct	0 ms	428 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	420 KB	Output is correct
23	Correct	1 ms	420 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	428 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	420 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	1 ms	424 KB	Output is correct
34	Correct	0 ms	468 KB	Output is correct
35	Correct	1 ms	424 KB	Output is correct
36	Correct	1 ms	468 KB	Output is correct
37	Correct	1 ms	468 KB	Output is correct
38	Correct	1 ms	468 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct
40	Correct	1 ms	424 KB	Output is correct
41	Correct	1 ms	468 KB	Output is correct
42	Correct	0 ms	468 KB	Output is correct
43	Correct	1 ms	468 KB	Output is correct
44	Correct	1 ms	468 KB	Output is correct
45	Correct	1 ms	468 KB	Output is correct
46	Correct	1 ms	468 KB	Output is correct
47	Correct	1 ms	468 KB	Output is correct
48	Correct	1 ms	468 KB	Output is correct
49	Correct	1 ms	468 KB	Output is correct
50	Correct	1 ms	468 KB	Output is correct
51	Correct	1 ms	420 KB	Output is correct
52	Correct	1 ms	468 KB	Output is correct
53	Correct	1 ms	468 KB	Output is correct
54	Correct	1 ms	340 KB	Output is correct
55	Correct	10 ms	24496 KB	Output is correct
56	Correct	1 ms	540 KB	Output is correct
57	Correct	7 ms	16596 KB	Output is correct
58	Correct	32 ms	19648 KB	Output is correct
59	Correct	244 ms	101268 KB	Output is correct
60	Correct	258 ms	101372 KB	Output is correct
61	Correct	238 ms	101236 KB	Output is correct
62	Correct	1 ms	468 KB	Output is correct
63	Correct	239 ms	100336 KB	Output is correct
64	Runtime error	378 ms	262144 KB	Execution killed with signal 9
65	Halted	0 ms	0 KB	-