Submission #217168

#	Time	Username	Problem	Language	Result	Execution time	Memory
217168		rama_pang	Stray Cat (JOI20_stray)	C++14	100 / 100	100 ms	18116 KiB

Anthony

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

Catherine

#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 (stderr)

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 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9