結果

問題 No.274 The Wall
ユーザー te-shte-sh
提出日時 2017-06-07 17:02:30
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 2,579 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 150,452 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-03 13:57:45
合計ジャッジ時間 3,671 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 WA -
testcase_10 AC 2 ms
4,380 KB
testcase_11 WA -
testcase_12 AC 47 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 12 ms
4,376 KB
testcase_15 AC 26 ms
4,380 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 48 ms
4,376 KB
testcase_20 AC 55 ms
4,380 KB
testcase_21 AC 57 ms
4,384 KB
testcase_22 AC 60 ms
4,380 KB
testcase_23 AC 60 ms
4,504 KB
testcase_24 AC 60 ms
4,380 KB
testcase_25 AC 61 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

void main()
{
  calc2();
}

auto calc1()
{
  auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1];

  auto g = new bool[][](n, m);
  foreach (i; 0..n) {
    auto rd2 = readln.split.to!(size_t[]), l = rd2[0], r = rd2[1] + 1;
    foreach (j; l..r) g[i][j] = true;
  }

  auto ci = new int[](m);
  foreach (i; 0..m)
    ci[i] = g.transversal(i).count!"a".to!int;

  if (m % 2 && ci[m/2+1] >= 2) {
    writeln("NO");
    return;
  }

  foreach (i; 0..m/2)
    if (ci[i] + ci[$-i-1] >= 3) {
      writeln("NO");
      return;
    }

  writeln("YES");
}

auto calc2()
{
  auto rd1 = readln.split.to!(int[]), n = rd1[0], m = rd1[1];

  struct LR
  {
    int l, r;

    auto isOverlap(LR rhs) { return l <= rhs.r && rhs.l <= r; }
    auto reversed() { return LR(m - r - 1, m - l - 1); }
  }

  auto lri = n.iota.map!(_ => readln.split.to!(int[])).map!(rd2 => LR(rd2[0], rd2[1])).array;

  auto sat = TwoSAT(n);

  foreach (i; 0..n-1)
    foreach (j; i+1..n) {
      if (lri[i].isOverlap(lri[j]) && lri[i].isOverlap(lri[j].reversed)) {
        writeln([i, j]);
        return;
      }

      if (lri[i].isOverlap(lri[j])) {
        sat.addClause(i, j);
        sat.addClause(~i, ~j);
      } else if (lri[i].isOverlap(lri[j].reversed)) {
        sat.addClause(i, ~j);
        sat.addClause(~i, j);
      }
    }

  writeln(sat.solve() ? "YES" : "NO");
}

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