oj.uz

Submission #212683

# Submission time Handle Problem Language Result Execution time Memory
212683 2020-03-24T05:25:05 Z rama_pang Stray Cat (JOI20_stray) C++14
91 / 100
 121 ms 17532 KB 
#include "Anthony.h"
#include "bits/stdc++.h"
using namespace std;

namespace {

int N, M, A, B;

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

      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 && adj[i].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 = 3 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;
      }

      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 {
        return -1;
      }
    } 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:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i + 4 < String.size(); i++) {
                       ~~~~~~^~~~~~~~~~~~~~~
Anthony.cpp: At global scope:
Anthony.cpp:7:14: warning: '{anonymous}::B' defined but not used [-Wunused-variable]
 int N, M, A, B;
              ^
Anthony.cpp:7:11: warning: '{anonymous}::A' defined but not used [-Wunused-variable]
 int N, M, A, B;
           ^
Anthony.cpp:7:8: warning: '{anonymous}::M' defined but not used [-Wunused-variable]
 int N, M, A, B;
        ^
Anthony.cpp:7:5: warning: '{anonymous}::N' defined but not used [-Wunused-variable]
 int N, M, A, B;
     ^

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:216:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
Catherine.cpp: At global scope:
Catherine.cpp:67: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 74 ms 16244 KB Output is correct
2 Correct 11 ms 772 KB Output is correct
3 Correct 52 ms 15840 KB Output is correct
4 Correct 80 ms 17532 KB Output is correct
5 Correct 89 ms 17524 KB Output is correct
6 Correct 69 ms 16256 KB Output is correct
7 Correct 62 ms 16364 KB Output is correct
8 Correct 79 ms 16896 KB Output is correct
9 Correct 71 ms 16888 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16244 KB Output is correct
2 Correct 11 ms 772 KB Output is correct
3 Correct 52 ms 15840 KB Output is correct
4 Correct 80 ms 17532 KB Output is correct
5 Correct 89 ms 17524 KB Output is correct
6 Correct 69 ms 16256 KB Output is correct
7 Correct 62 ms 16364 KB Output is correct
8 Correct 79 ms 16896 KB Output is correct
9 Correct 71 ms 16888 KB Output is correct
10 Correct 59 ms 14072 KB Output is correct
11 Correct 82 ms 14076 KB Output is correct
12 Correct 57 ms 14004 KB Output is correct
13 Correct 60 ms 14024 KB Output is correct
14 Correct 60 ms 14356 KB Output is correct
15 Correct 77 ms 14540 KB Output is correct
16 Correct 120 ms 17140 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13948 KB Output is correct
2 Correct 10 ms 908 KB Output is correct
3 Correct 57 ms 13692 KB Output is correct
4 Correct 81 ms 15308 KB Output is correct
5 Correct 87 ms 15332 KB Output is correct
6 Correct 62 ms 13840 KB Output is correct
7 Correct 64 ms 13948 KB Output is correct
8 Correct 73 ms 14716 KB Output is correct
9 Correct 78 ms 14668 KB Output is correct
10 Correct 64 ms 14452 KB Output is correct
11 Correct 69 ms 14436 KB Output is correct
12 Correct 71 ms 14452 KB Output is correct
13 Correct 75 ms 14324 KB Output is correct
14 Correct 81 ms 14760 KB Output is correct
15 Correct 79 ms 14600 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13948 KB Output is correct
2 Correct 10 ms 908 KB Output is correct
3 Correct 57 ms 13692 KB Output is correct
4 Correct 81 ms 15308 KB Output is correct
5 Correct 87 ms 15332 KB Output is correct
6 Correct 62 ms 13840 KB Output is correct
7 Correct 64 ms 13948 KB Output is correct
8 Correct 73 ms 14716 KB Output is correct
9 Correct 78 ms 14668 KB Output is correct
10 Correct 64 ms 14452 KB Output is correct
11 Correct 69 ms 14436 KB Output is correct
12 Correct 71 ms 14452 KB Output is correct
13 Correct 75 ms 14324 KB Output is correct
14 Correct 81 ms 14760 KB Output is correct
15 Correct 79 ms 14600 KB Output is correct
16 Correct 55 ms 12280 KB Output is correct
17 Correct 61 ms 12264 KB Output is correct
18 Correct 58 ms 12240 KB Output is correct
19 Correct 57 ms 12144 KB Output is correct
20 Correct 69 ms 12656 KB Output is correct
21 Correct 60 ms 12564 KB Output is correct
22 Correct 78 ms 14844 KB Output is correct
23 Correct 62 ms 12284 KB Output is correct
24 Correct 60 ms 12156 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 908 KB Output is correct
2 Correct 16 ms 772 KB Output is correct
3 Correct 15 ms 1096 KB Output is correct
4 Correct 14 ms 1164 KB Output is correct
5 Correct 15 ms 1244 KB Output is correct
6 Correct 16 ms 1164 KB Output is correct
7 Correct 18 ms 1328 KB Output is correct
8 Correct 16 ms 1292 KB Output is correct
9 Correct 15 ms 1164 KB Output is correct
10 Correct 15 ms 1292 KB Output is correct
11 Correct 16 ms 1196 KB Output is correct
12 Correct 17 ms 1352 KB Output is correct
13 Correct 15 ms 1380 KB Output is correct
14 Correct 15 ms 1172 KB Output is correct
15 Correct 15 ms 1164 KB Output is correct
16 Correct 15 ms 1084 KB Output is correct
17 Correct 15 ms 1172 KB Output is correct
18 Correct 17 ms 1108 KB Output is correct
19 Correct 14 ms 1300 KB Output is correct
20 Correct 14 ms 1164 KB Output is correct
21 Correct 17 ms 1172 KB Output is correct
22 Correct 14 ms 1172 KB Output is correct
23 Correct 15 ms 1036 KB Output is correct
24 Correct 17 ms 1036 KB Output is correct
25 Correct 18 ms 1172 KB Output is correct
26 Correct 15 ms 1028 KB Output is correct
27 Correct 16 ms 1152 KB Output is correct
28 Correct 16 ms 1172 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13836 KB Output is correct
2 Correct 101 ms 15348 KB Output is correct
3 Correct 16 ms 920 KB Output is correct
4 Correct 78 ms 13536 KB Output is correct
5 Correct 104 ms 17004 KB Output is correct
6 Correct 110 ms 17036 KB Output is correct
7 Correct 92 ms 16120 KB Output is correct
8 Correct 83 ms 16236 KB Output is correct
9 Correct 108 ms 17004 KB Output is correct
10 Correct 117 ms 17132 KB Output is correct
11 Correct 98 ms 17048 KB Output is correct
12 Correct 105 ms 17132 KB Output is correct
13 Correct 106 ms 17068 KB Output is correct
14 Correct 105 ms 17172 KB Output is correct
15 Correct 101 ms 17136 KB Output is correct
16 Correct 113 ms 17016 KB Output is correct
17 Correct 103 ms 16644 KB Output is correct
18 Correct 106 ms 16728 KB Output is correct
19 Correct 100 ms 16752 KB Output is correct
20 Correct 113 ms 16748 KB Output is correct
21 Correct 108 ms 16756 KB Output is correct
22 Correct 113 ms 16752 KB Output is correct
23 Correct 94 ms 13716 KB Output is correct
24 Correct 93 ms 13812 KB Output is correct
25 Correct 96 ms 14404 KB Output is correct
26 Correct 98 ms 14520 KB Output is correct
27 Correct 113 ms 15264 KB Output is correct
28 Correct 106 ms 15388 KB Output is correct
29 Correct 119 ms 15444 KB Output is correct
30 Correct 104 ms 15528 KB Output is correct
31 Correct 120 ms 13676 KB Output is correct
32 Correct 93 ms 13924 KB Output is correct
33 Correct 104 ms 14344 KB Output is correct
34 Correct 99 ms 14300 KB Output is correct
35 Correct 92 ms 15260 KB Output is correct
36 Correct 114 ms 15268 KB Output is correct
37 Correct 113 ms 15212 KB Output is correct
38 Correct 103 ms 15200 KB Output is correct
39 Correct 95 ms 15212 KB Output is correct
40 Correct 115 ms 15072 KB Output is correct
41 Correct 121 ms 15852 KB Output is correct
42 Correct 115 ms 15860 KB Output is correct
43 Correct 96 ms 15984 KB Output is correct
44 Correct 97 ms 15980 KB Output is correct
45 Correct 108 ms 16020 KB Output is correct
46 Correct 106 ms 15964 KB Output is correct
47 Correct 89 ms 14984 KB Output is correct
48 Correct 106 ms 15172 KB Output is correct
49 Correct 107 ms 14872 KB Output is correct
50 Correct 102 ms 15060 KB Output is correct
51 Correct 107 ms 14196 KB Output is correct
52 Correct 81 ms 13932 KB Output is correct
53 Correct 83 ms 13820 KB Output is correct
54 Correct 94 ms 13944 KB Output is correct
55 Correct 79 ms 13856 KB Output is correct
56 Correct 84 ms 13940 KB Output is correct
57 Correct 89 ms 13660 KB Output is correct
58 Correct 80 ms 13652 KB Output is correct
59 Correct 100 ms 13952 KB Output is correct
60 Correct 102 ms 13968 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13732 KB Output is correct
2 Correct 98 ms 15092 KB Output is correct
3 Correct 13 ms 832 KB Output is correct
4 Correct 89 ms 13588 KB Output is correct
5 Correct 115 ms 17092 KB Output is correct
6 Correct 97 ms 17020 KB Output is correct
7 Correct 106 ms 16100 KB Output is correct
8 Correct 99 ms 16224 KB Output is correct
9 Correct 119 ms 17016 KB Output is correct
10 Correct 110 ms 17164 KB Output is correct
11 Correct 100 ms 17124 KB Output is correct
12 Incorrect 89 ms 17156 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -