oj.uz

Submission #217168

# Submission time Handle Problem Language Result Execution time Memory
217168 2020-03-29T07:13:55 Z rama_pang Stray Cat (JOI20_stray) C++14
100 / 100
 100 ms 18116 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

vector<int> Bfs(int N, vector<vector<int>> adj) {
  queue<int> q;
  q.emplace(0);

  vector<int> dist(N, -1);
  dist[0] = 0;

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &v : adj[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.emplace(v);
      }
    }
  }

  return dist;
}

vector<int> SolveGeneral(int N, int M, int A, int B, vector<int> U, vector<int> V) { // solve for A = 3 with B = 0 for any graph
  vector<vector<int>> adj(N);
  for (int i = 0; i < M; i++) {
    adj[U[i]].emplace_back(V[i]);
    adj[V[i]].emplace_back(U[i]);
  }

  vector<int> dist = Bfs(N, adj);

  vector<int> res;
  for (int i = 0; i < M; i++) {
    if (dist[U[i]] > dist[V[i]]) swap(U[i], V[i]);
    res.emplace_back(dist[U[i]] % 3);
  }

  return res;

}

vector<int> Mask;

void GenerateMask() {
  for (int len = 1; true; len++) {
    for (int mask = 0; mask < (1 << len); mask++) {
      vector<int> String;
      for (int i = 0; i < len; i++) {
        if (mask & (1 << i)) {
          String.emplace_back(1);
        } else {
          String.emplace_back(0);
        }
      }

      {
        int cnt = 0;
        while (String.size() < 100) {
          String.emplace_back(String[cnt]);
          cnt++;
        }
      }

      map<vector<int>, int> direction;
      for (int i = 0; i + 4 < String.size(); i++) {
        vector<int> cur;
        for (int j = i; j < i + 5; j++) {
          cur.emplace_back(String[j]);
        }
        direction[cur] |= 1;
        reverse(begin(cur), end(cur));
        direction[cur] |= 2;
      }
      
      { // when starting the sequence, adj[n].size() == 2 && adj[p].size() != 2, edge (n, p) can either be 0 or 1 (4 true bits from Mask)
        vector<int> cur;
        cur.emplace_back(0);
        for (int i = 0; i < 4; i++) {
          cur.emplace_back(String[i]);
        }
        // wrong direction
        direction[cur] |= 1;
        cur.front() ^= 1;
        direction[cur] |= 1;

        // right direction
        reverse(begin(cur), end(cur));
        direction[cur] |= 2;
        cur.back() ^= 1;
        direction[cur] |= 2;
      }

      bool can = true;

      for (auto &i : direction) {
        if (i.second == 3) {
          can = false;
        }
      }

      if (can) {
        for (int i = 0; i < len; i++) {
          Mask.emplace_back(String[i]);
        }
        return;
      }
    }
  }
}

vector<int> ans;
map<pair<int, int>, int> UV_id;

void Dfs(int n, int p, int cnt, const vector<vector<int>> &adj, vector<int> &color) {
  if (cnt != -1) {
    cnt %= Mask.size();
  }

  if (p != -1) {
    if (cnt == -1) {
      color[n] = color[p] ^ 1;
    } else {
      color[n] = Mask[cnt];
    }
    ans[UV_id[{n, p}]] = color[n];
  } else {
    color[n] = 1;
  }

  for (auto &i : adj[n]) if (i != p) {
    if (n != 0 && adj[n].size() == 2) {
      Dfs(i, n, cnt + 1, adj, color);
    } else {
      Dfs(i, n, -1, adj, color);
    }
  }
}

vector<int> SolveTree(int N, int M, int A, int B, vector<int> U, vector<int> V) { // solve for A = 2 with B = 6 for a tree
  vector<vector<int>> adj(N);
  ans.resize(M);

  for (int i = 0; i < M; i++) {
    adj[U[i]].emplace_back(V[i]);
    adj[V[i]].emplace_back(U[i]);
    UV_id[{U[i], V[i]}] = UV_id[{V[i], U[i]}] = i;
  }

  GenerateMask();
  vector<int> parent_edge_color(N, -1);
  Dfs(0, -1, -1, adj, parent_edge_color);

  for (int i = 0; i < M; i++) {
    assert(0 <= ans[i] && ans[i] < A);
  }

  return ans;
}

}  // namespace

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
  if (A >= 3) {
    return SolveGeneral(N, M, A, B, U, V); // A = 3 and B = 0
  } else {
    return SolveTree(N, M, A, B, U, V); // A = 2 and B >= 6
  }
}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

set<vector<int>> RIGHT_DIRECTION;
set<vector<int>> WRONG_DIRECTION;

void GenerateMask() {
  for (int len = 1; true; len++) {
    for (int mask = 0; mask < (1 << len); mask++) {
      vector<int> String;
      for (int i = 0; i < len; i++) {
        if (mask & (1 << i)) {
          String.emplace_back(1);
        } else {
          String.emplace_back(0);
        }
      }

      {
        int cnt = 0;
        while (String.size() < 100) {
          String.emplace_back(String[cnt]);
          cnt++;
        }
      }

      map<vector<int>, int> direction;
      for (int i = 0; i + 4 < String.size(); i++) {
        vector<int> cur;
        for (int j = i; j < i + 5; j++) {
          cur.emplace_back(String[j]);
        }
        direction[cur] |= 1;
        reverse(begin(cur), end(cur));
        direction[cur] |= 2;
      }

      { // when starting the sequence, adj[n].size() == 2 && adj[p].size() != 2, edge (n, p) can either be 0 or 1 (4 true bits from Mask)
        vector<int> cur;
        cur.emplace_back(0);
        for (int i = 0; i < 4; i++) {
          cur.emplace_back(String[i]);
        }
        // wrong direction
        direction[cur] |= 1;
        cur.front() ^= 1;
        direction[cur] |= 1;

        // right direction
        reverse(begin(cur), end(cur));
        direction[cur] |= 2;
        cur.back() ^= 1;
        direction[cur] |= 2;
      }

      bool can = true;

      for (auto &i : direction) {
        if (i.second == 1 || i.second == 2) {
          continue;
        }
        can = false;
      }

      if (can) {
        for (auto &i : direction) {
          if (i.second == 1) { // wrong direction
            WRONG_DIRECTION.emplace(i.first);
          } else if (i.second == 2) {
            RIGHT_DIRECTION.emplace(i.first);
          } else {
            assert(false);
          }
        }
        return;
      }
    }
  }
}

int A, B;
int variable_example = 0;

int SolveGeneral(vector<int> y) { // solve for A = 3 with B = 0 for any graph
  // case: there is only one possible edge to go
  if (y[0] == 0 && y[1] == 0) {
    return 2;
  } else if (y[0] == 0 && y[2] == 0) {
    return 1;
  } else if (y[1] == 0 && y[2] == 0) {
    return 0;
  }

  // general case
  if (y[0] == 0) { // case 12, go to 1
    return 1;
  } else if (y[1] == 0) { // case 20, go to 2
    return 2;
  } else if (y[2] == 0) { // case 01, go to 1
    return 0;
  }

  // this should never be triggered
  return -1;
}

int SolveTree(vector<int> y) { // solve for A = 2 with B = 12 for a tree
  static int determined = 0; // determined the correct way
  static int last = -1;

  // if not yet determined
  static vector<int> read;

  if (last == -1) {
    if (y[0] + y[1] == 2) {
      if (y[0] == 1 && y[1] == 1) {
        read.emplace_back(1);
        read.emplace_back(0);
        return last = 0;
      } else if (y[0] == 2 && y[1] == 0) {
        read.emplace_back(0);
        read.emplace_back(0);
        return last = 0;
      } else if (y[0] == 0 && y[1] == 2) {
        read.emplace_back(1);
        read.emplace_back(1);
        return last = 1;
      }
    } else {
      determined = 1;
      if (y[0] == 1) {
        return last = 0;
      } else if (y[1] == 1) {
        return last = 1;
      }
    }
  }

  if (y[0] == 0 && y[1] == 0) {
    determined = 1;
    return -1;
  }

  y[last]++;
  if (determined) {
    if (y[0] + y[1] == 2) {
      y[last]--;
      if (y[0] == 1) {
        return last = 0;
      } else if (y[1] == 1) {
        return last = 1;
      } else {
        return -1;
      }
    } else if (y[0] == 1) {
      if (last == 0) {
        return -1;
      } else {
        return last = 0;
      }
    } else if (y[1] == 1) {
      if (last == 1) {
        return -1;
      } else {
        return last = 1;
      }
    } else {
      return -1;
    }
  }

  if (y[0] + y[1] != 2) {
    determined = 1;
    if (y[0] == 1) {
      if (last == 0) {
        return -1;
      } else {
        return last = 0;
      }
    } else if (y[1] == 1) {
      if (last == 1) {
        return -1;
      } else {
        return last = 1;
      }
    } else {
      return -1;
    }
  }

  y[last]--;

  if (read.size() < 4) {
    if (y[0] == 1) {
      read.emplace_back(0);
      return last = 0;
    } else if (y[1] == 1) {
      read.emplace_back(1);
      return last = 1;
    } else {
      determined = 1;
      return -1;
    }
  } else if (read.size() == 4) {
    if (y[0] == 1) {
      read.emplace_back(0);
    } else if (y[1] == 1) {
      read.emplace_back(1);
    } else {
      determined = 1;
      return -1;
    }
  } 
  
  if (read.size() == 5) {
    determined = 1;
    if (WRONG_DIRECTION.count(read) == 1) {
      return -1;
    } else if (RIGHT_DIRECTION.count(read) == 1) {
      if (y[0] == 1) {
        return last = 0;
      } else if (y[1] == 1) {
        return last = 1;
      } else {
        assert(false);
      }
    } else {
      return -1;
    }
  }
}

}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  GenerateMask();
}

int Move(vector<int> y) {
  if (A >= 3) {
    return SolveGeneral(y);
  } else {
    return SolveTree(y);
  }
}

Compilation message

Anthony.cpp: In function 'void {anonymous}::GenerateMask()':
Anthony.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i + 4 < String.size(); i++) {
                       ~~~~~~^~~~~~~~~~~~~~~

Catherine.cpp: In function 'void {anonymous}::GenerateMask()':
Catherine.cpp:31:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i + 4 < String.size(); i++) {
                       ~~~~~~^~~~~~~~~~~~~~~
Catherine.cpp: In function 'int {anonymous}::SolveTree(std::vector<int>)':
Catherine.cpp:234:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
Catherine.cpp: At global scope:
Catherine.cpp:85:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
 int variable_example = 0;
     ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16844 KB Output is correct
2 Correct 11 ms 780 KB Output is correct
3 Correct 50 ms 16252 KB Output is correct
4 Correct 70 ms 17996 KB Output is correct
5 Correct 71 ms 18116 KB Output is correct
6 Correct 56 ms 16644 KB Output is correct
7 Correct 61 ms 16784 KB Output is correct
8 Correct 66 ms 17452 KB Output is correct
9 Correct 64 ms 17476 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16844 KB Output is correct
2 Correct 11 ms 780 KB Output is correct
3 Correct 50 ms 16252 KB Output is correct
4 Correct 70 ms 17996 KB Output is correct
5 Correct 71 ms 18116 KB Output is correct
6 Correct 56 ms 16644 KB Output is correct
7 Correct 61 ms 16784 KB Output is correct
8 Correct 66 ms 17452 KB Output is correct
9 Correct 64 ms 17476 KB Output is correct
10 Correct 53 ms 14432 KB Output is correct
11 Correct 53 ms 14544 KB Output is correct
12 Correct 56 ms 14548 KB Output is correct
13 Correct 54 ms 14536 KB Output is correct
14 Correct 56 ms 14740 KB Output is correct
15 Correct 64 ms 15116 KB Output is correct
16 Correct 66 ms 17592 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 14524 KB Output is correct
2 Correct 11 ms 776 KB Output is correct
3 Correct 48 ms 13928 KB Output is correct
4 Correct 70 ms 15792 KB Output is correct
5 Correct 68 ms 15944 KB Output is correct
6 Correct 55 ms 14504 KB Output is correct
7 Correct 58 ms 14420 KB Output is correct
8 Correct 67 ms 15308 KB Output is correct
9 Correct 63 ms 15148 KB Output is correct
10 Correct 57 ms 15032 KB Output is correct
11 Correct 59 ms 15036 KB Output is correct
12 Correct 64 ms 14792 KB Output is correct
13 Correct 59 ms 15040 KB Output is correct
14 Correct 62 ms 15288 KB Output is correct
15 Correct 63 ms 15136 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 14524 KB Output is correct
2 Correct 11 ms 776 KB Output is correct
3 Correct 48 ms 13928 KB Output is correct
4 Correct 70 ms 15792 KB Output is correct
5 Correct 68 ms 15944 KB Output is correct
6 Correct 55 ms 14504 KB Output is correct
7 Correct 58 ms 14420 KB Output is correct
8 Correct 67 ms 15308 KB Output is correct
9 Correct 63 ms 15148 KB Output is correct
10 Correct 57 ms 15032 KB Output is correct
11 Correct 59 ms 15036 KB Output is correct
12 Correct 64 ms 14792 KB Output is correct
13 Correct 59 ms 15040 KB Output is correct
14 Correct 62 ms 15288 KB Output is correct
15 Correct 63 ms 15136 KB Output is correct
16 Correct 53 ms 12748 KB Output is correct
17 Correct 50 ms 12620 KB Output is correct
18 Correct 53 ms 12644 KB Output is correct
19 Correct 51 ms 12516 KB Output is correct
20 Correct 63 ms 13132 KB Output is correct
21 Correct 55 ms 12940 KB Output is correct
22 Correct 61 ms 15432 KB Output is correct
23 Correct 53 ms 12664 KB Output is correct
24 Correct 58 ms 12872 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1428 KB Output is correct
2 Correct 12 ms 904 KB Output is correct
3 Correct 14 ms 1068 KB Output is correct
4 Correct 14 ms 1168 KB Output is correct
5 Correct 14 ms 1368 KB Output is correct
6 Correct 14 ms 1372 KB Output is correct
7 Correct 14 ms 1176 KB Output is correct
8 Correct 14 ms 1268 KB Output is correct
9 Correct 14 ms 1392 KB Output is correct
10 Correct 14 ms 1168 KB Output is correct
11 Correct 14 ms 1180 KB Output is correct
12 Correct 14 ms 1260 KB Output is correct
13 Correct 14 ms 1292 KB Output is correct
14 Correct 14 ms 1276 KB Output is correct
15 Correct 14 ms 1408 KB Output is correct
16 Correct 15 ms 1304 KB Output is correct
17 Correct 14 ms 1408 KB Output is correct
18 Correct 14 ms 1060 KB Output is correct
19 Correct 14 ms 1060 KB Output is correct
20 Correct 14 ms 1056 KB Output is correct
21 Correct 14 ms 1052 KB Output is correct
22 Correct 14 ms 1044 KB Output is correct
23 Correct 14 ms 1044 KB Output is correct
24 Correct 15 ms 1188 KB Output is correct
25 Correct 14 ms 1056 KB Output is correct
26 Correct 14 ms 1040 KB Output is correct
27 Correct 15 ms 1044 KB Output is correct
28 Correct 15 ms 1052 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14080 KB Output is correct
2 Correct 77 ms 15568 KB Output is correct
3 Correct 12 ms 780 KB Output is correct
4 Correct 65 ms 13924 KB Output is correct
5 Correct 84 ms 17668 KB Output is correct
6 Correct 86 ms 17572 KB Output is correct
7 Correct 74 ms 16804 KB Output is correct
8 Correct 83 ms 16796 KB Output is correct
9 Correct 84 ms 17528 KB Output is correct
10 Correct 86 ms 17556 KB Output is correct
11 Correct 87 ms 17684 KB Output is correct
12 Correct 91 ms 17680 KB Output is correct
13 Correct 86 ms 17564 KB Output is correct
14 Correct 86 ms 17704 KB Output is correct
15 Correct 100 ms 17688 KB Output is correct
16 Correct 86 ms 17688 KB Output is correct
17 Correct 80 ms 17312 KB Output is correct
18 Correct 83 ms 17316 KB Output is correct
19 Correct 88 ms 17456 KB Output is correct
20 Correct 83 ms 17312 KB Output is correct
21 Correct 81 ms 17308 KB Output is correct
22 Correct 83 ms 17308 KB Output is correct
23 Correct 72 ms 14076 KB Output is correct
24 Correct 71 ms 14060 KB Output is correct
25 Correct 74 ms 14796 KB Output is correct
26 Correct 78 ms 14796 KB Output is correct
27 Correct 78 ms 15704 KB Output is correct
28 Correct 79 ms 15740 KB Output is correct
29 Correct 79 ms 15940 KB Output is correct
30 Correct 80 ms 15996 KB Output is correct
31 Correct 72 ms 14080 KB Output is correct
32 Correct 74 ms 14080 KB Output is correct
33 Correct 72 ms 14656 KB Output is correct
34 Correct 76 ms 14732 KB Output is correct
35 Correct 78 ms 15676 KB Output is correct
36 Correct 78 ms 15672 KB Output is correct
37 Correct 83 ms 15560 KB Output is correct
38 Correct 79 ms 15680 KB Output is correct
39 Correct 78 ms 15676 KB Output is correct
40 Correct 78 ms 15672 KB Output is correct
41 Correct 83 ms 16572 KB Output is correct
42 Correct 81 ms 16552 KB Output is correct
43 Correct 81 ms 16544 KB Output is correct
44 Correct 81 ms 16568 KB Output is correct
45 Correct 80 ms 16520 KB Output is correct
46 Correct 81 ms 16552 KB Output is correct
47 Correct 78 ms 15516 KB Output is correct
48 Correct 81 ms 15476 KB Output is correct
49 Correct 77 ms 15400 KB Output is correct
50 Correct 77 ms 15520 KB Output is correct
51 Correct 77 ms 14492 KB Output is correct
52 Correct 72 ms 14488 KB Output is correct
53 Correct 74 ms 14436 KB Output is correct
54 Correct 73 ms 14492 KB Output is correct
55 Correct 78 ms 14492 KB Output is correct
56 Correct 73 ms 14292 KB Output is correct
57 Correct 78 ms 14196 KB Output is correct
58 Correct 72 ms 14256 KB Output is correct
59 Correct 75 ms 14652 KB Output is correct
60 Correct 73 ms 14464 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 14084 KB Output is correct
2 Correct 76 ms 15444 KB Output is correct
3 Correct 14 ms 784 KB Output is correct
4 Correct 65 ms 13888 KB Output is correct
5 Correct 83 ms 17688 KB Output is correct
6 Correct 84 ms 17600 KB Output is correct
7 Correct 79 ms 16632 KB Output is correct
8 Correct 75 ms 16788 KB Output is correct
9 Correct 86 ms 17696 KB Output is correct
10 Correct 87 ms 17684 KB Output is correct
11 Correct 84 ms 17532 KB Output is correct
12 Correct 88 ms 17680 KB Output is correct
13 Correct 87 ms 17684 KB Output is correct
14 Correct 90 ms 17836 KB Output is correct
15 Correct 86 ms 17688 KB Output is correct
16 Correct 84 ms 17692 KB Output is correct
17 Correct 88 ms 17308 KB Output is correct
18 Correct 81 ms 17152 KB Output is correct
19 Correct 90 ms 17308 KB Output is correct
20 Correct 81 ms 17292 KB Output is correct
21 Correct 90 ms 17288 KB Output is correct
22 Correct 93 ms 17312 KB Output is correct
23 Correct 73 ms 14068 KB Output is correct
24 Correct 73 ms 14204 KB Output is correct
25 Correct 78 ms 14936 KB Output is correct
26 Correct 78 ms 14688 KB Output is correct
27 Correct 79 ms 15688 KB Output is correct
28 Correct 79 ms 15688 KB Output is correct
29 Correct 83 ms 15900 KB Output is correct
30 Correct 78 ms 15924 KB Output is correct
31 Correct 71 ms 14040 KB Output is correct
32 Correct 75 ms 14076 KB Output is correct
33 Correct 73 ms 14692 KB Output is correct
34 Correct 75 ms 14796 KB Output is correct
35 Correct 78 ms 15688 KB Output is correct
36 Correct 79 ms 15564 KB Output is correct
37 Correct 79 ms 15676 KB Output is correct
38 Correct 79 ms 15692 KB Output is correct
39 Correct 81 ms 15672 KB Output is correct
40 Correct 78 ms 15660 KB Output is correct
41 Correct 80 ms 16544 KB Output is correct
42 Correct 88 ms 16568 KB Output is correct
43 Correct 86 ms 16576 KB Output is correct
44 Correct 81 ms 16544 KB Output is correct
45 Correct 97 ms 16544 KB Output is correct
46 Correct 82 ms 16556 KB Output is correct
47 Correct 81 ms 15448 KB Output is correct
48 Correct 79 ms 15524 KB Output is correct
49 Correct 88 ms 15392 KB Output is correct
50 Correct 78 ms 15512 KB Output is correct
51 Correct 75 ms 14496 KB Output is correct
52 Correct 75 ms 14492 KB Output is correct
53 Correct 73 ms 14496 KB Output is correct
54 Correct 83 ms 14480 KB Output is correct
55 Correct 76 ms 14488 KB Output is correct
56 Correct 76 ms 14500 KB Output is correct
57 Correct 73 ms 14244 KB Output is correct
58 Correct 74 ms 14240 KB Output is correct
59 Correct 74 ms 14532 KB Output is correct
60 Correct 74 ms 14480 KB Output is correct