Submission

[PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP]

Score: 100

User: sleepntsheep

Problemset: Optimal Placement

Language: cpp

Time: 0.112 second

Submitted On: 2025-02-27 22:51:56

#include <stdio.h>
#include <stdlib.h>
#include <tuple>
#include <cassert>
#include <vector>

using namespace std;

int asgn[100000];

struct TwoSatSolver {
  int n_vars;
  int n_vertices;
  vector<vector<int>> adj, adj_t;
  vector<bool> used;
  vector<int> order, comp;
  vector<bool> assignment;

  TwoSatSolver(int _n_vars) : n_vars(_n_vars), n_vertices(2 * n_vars), adj(n_vertices), adj_t(n_vertices), used(n_vertices), order(), comp(n_vertices, -1), assignment(n_vars) {
    order.reserve(n_vertices);
  }
  void dfs1(int v) {
    used[v] = true;
    for (int u : adj[v]) {
      if (!used[u])
        dfs1(u);
    }
    order.push_back(v);
  }

  void dfs2(int v, int cl) {
    comp[v] = cl;
    for (int u : adj_t[v]) {
      if (comp[u] == -1)
        dfs2(u, cl);
    }
  }

  bool solve_2SAT() {
    order.clear();
    used.assign(n_vertices, false);
    for (int i = 0; i < n_vertices; ++i) {
      if (!used[i])
        dfs1(i);
    }

    comp.assign(n_vertices, -1);
    for (int i = 0, j = 0; i < n_vertices; ++i) {
      int v = order[n_vertices - i - 1];
      if (comp[v] == -1)
        dfs2(v, j++);
    }

    assignment.assign(n_vars, false);
    for (int i = 0; i < n_vertices; i += 2) {
      if (comp[i] == comp[i + 1])
        return false;
      assignment[i / 2] = comp[i] > comp[i + 1];
    }
    return true;
  }

  void add_disjunction(int a, bool na, int b, bool nb) {
    // na and nb signify whether a and b are to be negated 
    a = 2 * a ^ na;
    b = 2 * b ^ nb;
    int neg_a = a ^ 1;
    int neg_b = b ^ 1;
    adj[neg_a].push_back(b);
    adj[neg_b].push_back(a);
    adj_t[b].push_back(neg_a);
    adj_t[a].push_back(neg_b);
  }

  static void example_usage() {
    TwoSatSolver solver(3); // a, b, c
    solver.add_disjunction(0, false, 1, true);  //     a  v  not b
    solver.add_disjunction(0, true, 1, true);   // not a  v  not b
    solver.add_disjunction(1, false, 2, false); //     b  v      c
    solver.add_disjunction(0, false, 0, false); //     a  v      a
    assert(solver.solve_2SAT() == true);
  }
};

int main()
{
  int n, m;

  scanf("%d%d", &n, &m);

  vector<tuple<int, int, int, int>> flags;

  for (int i = 0; i < m; ++i) {
    int x, y, w, z;
    scanf("%d%d%d%d", &x, &y, &w, &z);
    flags.emplace_back(x, y, w, z);
  }

  auto canPlace = [&](int d) -> bool {
    TwoSatSolver solver(m + m);
    for (int i = 0; i < m; ++i)
    {
      solver.add_disjunction(i, false, i + m, false);
      solver.add_disjunction(i, true, i + m, true);
    }

    auto dis = [&](int x, int y, int w, int z)
    {
      return abs(x - w) + abs(y - z);
    };

    for (int i = 0; i < m; ++i)
    {
      auto [xi, yi, wi, zi] = flags[i];
      for (int j = 0; j < m; ++j)
      {
        if (i == j)
          continue;
        auto [xj, yj, wj, zj] = flags[j];

        if (dis(xi, yi, xj, yj) < d)
        {
          solver.add_disjunction(i, true, j, true);
        }

        if (dis(xi, yi, wj, zj) < d)
        {
          solver.add_disjunction(i, true, j + m, true);
          //solver.add_disjunction(i, true, j, false);
        }

        if (dis(wi, zi, xj, yj) < d)
        {
          solver.add_disjunction(i + m, true, j, true);
          //solver.add_disjunction(i, false, j, true);
        }

        if (dis(wi, zi, wj, zj) < d)
        {
          solver.add_disjunction(i + m, true, j + m, true);
          //solver.add_disjunction(i, false, j, false);
        }
      }
    }


    bool ret;
    ret = solver.solve_2SAT();
    //printf(" %d %d\n",d,(int)ret);

    if (ret)
    {
      for (int i = 0; i < m; ++i)
        asgn[i] = solver.assignment[i] ? 'A' : 'B';
    }
    return ret;
  };

  int low = 0, high = n + n, ans = 0;

  while (low <= high) {
    int mid = (low + high) / 2;

    if (canPlace(mid)) {
      ans = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  printf("%d\n", ans);

  canPlace(ans);

  for (int i = 0; i < m; ++i)
    putchar(asgn[i]);

  return 0;
}