結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー te-sh
提出日時 2017-12-15 11:57:02
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,197 bytes
コンパイル時間 705 ms
コンパイル使用メモリ 100,952 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 23:07:24
合計ジャッジ時間 2,255 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(16): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(18): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(34): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(36): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!int;
  auto u = new string[](n);
  foreach (i; 0..n) u[i] = readln.chomp;

  if (n > 52) {
    writeln("Impossible");
    return;
  }

  auto ts = TwoSAT(n);

  foreach (int i, ui; u) {
    auto sit = ui[0..1], tit = ui[1..3], sif = ui[0..2], tif = ui[2..3];
    foreach (int j, uj; u) {
      if (j <= i) continue;
      auto sjt = uj[0..1], tjt = uj[1..3], sjf = uj[0..2], tjf = uj[2..3];
      if (sit == sjt || tit == tjt) ts.addClause(~i, ~j);
      if (sit == tjf || tit == sjf) ts.addClause(~i, j);
      if (sif == tjt || tif == sjt) ts.addClause(i, ~j);
      if (sif == sjf || tif == tjf) ts.addClause(i, j);
    }
  }

  if (!ts.solve()) {
    writeln("Impossible");
    return;
  }

  auto idx = new int[](n*2);
  foreach (int i, oi; ts.ord) idx[oi+n] = i;

  foreach (int i, ui; u) {
    if (idx[~i+n] > idx[i+n]) writeln(ui[0..2], " ", ui[2..3]);
    else                      writeln(ui[0..1], " ", ui[1..3]);
  }
}

struct TwoSAT
{
  import std.algorithm;
  import std.stdio;

  int n;
  bool[] x;
  int[] num, col, ord;
  int[][] imp, rmp;

  this(int n)
  {
    this.n = n;
    auto n2 = n * 2;
    x = new bool[](n2);
    num = new int[](n2);
    col = new int[](n2);
    imp = new int[][](n2);
    rmp = new int[][](n2);
  }

  auto addClause(int u, int v)
  {
    if (u == ~v) {
      return;
    } else if (u == v) {
      x[u+n] = true;
    } else {
      imp[~u+n] ~= v;
      imp[~v+n] ~= u;
      rmp[u+n] ~= ~v;
      rmp[v+n] ~= ~u;
    }
  }

  auto solve() {
    foreach (u; -n..n)
      if (x[u+n]) visit(u, false);
    foreach (u; -n..n)
      if (x[u+n] && x[~u+n]) return false;
      else visit(u, 0);
    num = col.dup;
    ord.reverse();
    foreach (v; ord) rvisit(v, v);
    foreach (u; 0..n)
      if (col[u+n] == col[~u+n]) return false;
    return true;
  }

  private auto visit(int u, bool b)
  {
    if (num[u+n]++ > 0) return;
    x[u+n] |= b;
    foreach (v; imp[u+n]) visit(v, x[u+n]);
    ord ~= u;
  }

  private auto rvisit(int u, int k)
  {
    if (num[u+n]++ > 0) return;
    col[u+n] = k;
    foreach (v; rmp[u+n]) rvisit(v, k);
  }
}
0