結果

問題 No.382 シャイな人たち (2)
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-01-18 21:19:42
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 4,563 bytes
コンパイル時間 22,672 ms
コンパイル使用メモリ 672,276 KB
実行使用メモリ 21,752 KB
最終ジャッジ日時 2023-09-03 22:26:43
合計ジャッジ時間 41,101 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(59): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(61): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(69): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(71): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(85): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
Main.d(87): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


int root(int[] uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u]));
}
bool connect(int[] uf, int u, int v) {
  u = uf.root(u);
  v = uf.root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}

int[] independentSet(int[][] g, bool assumeConnected = false) {
  const n = cast(int)(g.length);
  if (n == 0) return [];
  if (n == 1) return [0];
  int[] ret;
  if (assumeConnected) {
    const degs = g.map!(us => cast(int)(us.length)).array;
    const uMin = cast(int)(degs.minIndex), uMax = cast(int)(degs.maxIndex);
    if (degs[uMax] <= 2) {
      // path or cycle
      ret ~= uMin;
      int t = -1, u = uMin;
      foreach (j; 1 .. (degs[uMin] == 1) ? n : (n - 1)) {
        const v = (g[u][0] != t) ? g[u][0] : g[u][1];
        t = u; u = v;
        if (j % 2 == 0) ret ~= u;
      }
    } else {
      const u0 = (degs[uMin] >= 2) ? uMax : uMin;
      // use u0
      {
        auto ids = new int[n];
        ids[] = -1; ids[u0] = -2;
        foreach (v; g[u0]) ids[v] = -2;
        int[] us;
        foreach (u; 0 .. n) if (ids[u] != -2) us ~= u;
        foreach (int j, u; us) ids[u] = j;
        auto gg = new int[][us.length];
        foreach (int j, u; us) foreach (v; g[u]) if (ids[v] != -2) gg[j] ~= ids[v];
        ret = u0 ~ independentSet(gg).map!(j => us[j]).array;
      }
      // do not use u0
      if (degs[uMin] >= 2) {
        auto ids = new int[n];
        int[] us;
        foreach (u; 0 .. n) if (u != u0) us ~= u;
        foreach (int j, u; us) ids[u] = j;
        auto gg = new int[][us.length];
        foreach (int j, u; us) foreach (v; g[u]) if (v != u0) gg[j] ~= ids[v];
        const res = independentSet(gg);
        if (ret.length < res.length) ret = res.map!(j => us[j]).array;
      }
    }
  } else {
    // solve for each connected component
    auto uf = new int[n];
    uf[] = -1;
    foreach (u; 0 .. n) foreach (v; g[u]) uf.connect(u, v);
    auto uss = new int[][n];
    foreach (u; 0 .. n) uss[uf.root(u)] ~= u;
    auto ids = new int[n];
    foreach (r; 0 .. n) if (uf[r] < 0) {
      foreach (int j, u; uss[r]) ids[u] = j;
      auto gg = new int[][uss[r].length];
      foreach (int j, u; uss[r]) foreach (v; g[u]) gg[j] ~= ids[v];
      const res = independentSet(gg, true);
      foreach (j; res) ret ~= uss[r][j];
    }
  }
  return ret;
}


int N;
long P;
long[][] F;

void main() {
  try {
    for (; ; ) {
/*
    S is given
    S=(S×12345) mod 1000003
    N=(S mod 120)+2
    S=(S×12345) mod 1000003
    P=S
    for(i=1; i<=N; i++){
        for(j=i+1; j<=N; j++){
            S=(S×12345) mod 1000003
            Fij=Fji=S
        }
    }
*/
      long S = readLong();
      S = (S * 12345) % 1000003;
      N = (S % 120) + 2;
      S = (S * 12345) % 1000003;
      P = S;
      F = new long[][](N, N);
      foreach (u; 0 .. N) {
        foreach (v; u + 1 .. N) {
          S = (S * 12345) % 1000003;
          F[u][v] = F[v][u] = S;
        }
      }
      stderr.writeln("N = ", N);
      
      auto g = new int[][N];
      foreach (u; 0 .. N) {
        foreach (v; 0 .. N) {
          if (u != v) {
            if (F[u][v] >= P) {
              g[u] ~= v;
            }
          }
        }
      }
      const res = independentSet(g);
      if (res.length == N) {
        writeln(-1);
      } else {
        writeln(res.length + 1);
        writeln(res.map!(u => u + 1).to!string.replaceAll(regex(`[\[\],]`), ""));
      }
    }
  } catch (EOFException e) {
  }
}
0