結果
| 問題 | No.1400 すごろくで世界旅行 |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2019-12-24 14:43:49 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 45,180 bytes |
| コンパイル時間 | 4,188 ms |
| コンパイル使用メモリ | 96,520 KB |
| 実行使用メモリ | 45,608 KB |
| 最終ジャッジ日時 | 2024-05-06 09:57:23 |
| 合計ジャッジ時間 | 6,786 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 47 ms
37,076 KB |
| testcase_01 | WA | - |
| testcase_02 | AC | 45 ms
36,940 KB |
| testcase_03 | AC | 66 ms
38,544 KB |
| testcase_04 | WA | - |
| testcase_05 | AC | 51 ms
37,428 KB |
| testcase_06 | AC | 105 ms
39,752 KB |
| testcase_07 | AC | 125 ms
40,572 KB |
| testcase_08 | AC | 68 ms
38,204 KB |
| testcase_09 | AC | 68 ms
37,544 KB |
| testcase_10 | AC | 90 ms
39,548 KB |
| testcase_11 | AC | 59 ms
37,260 KB |
| testcase_12 | AC | 269 ms
45,608 KB |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | AC | 46 ms
37,112 KB |
| testcase_20 | WA | - |
ソースコード
package yukicoder_3785;
import java.awt.Point;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.util.BitSet;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.function.UnaryOperator;
public class Main {
/** デバッグ用コードのお供に */
private static boolean DEBUG = false;
private final FastIO io;
private void solve(FastIO io, String[] args) {
/*
* author: 31536000
* 考察メモ
* 2回前に行けた全ての頂点は移動可能であるから、2個おきに辿り着く頂点集合を取ると全順序
* よって新たに増えた頂点のみを調べていけばよく、これはO(V)回の試行で終わるのでO(V^2/64)
* 全頂点を調べてもO(V^3/64)で間に合うよ
*/
int V, D;
boolean checkEdge = args.length != 0;
if (args.length != 0) {
FastIO src = new FastIO();
src.setInputStream(new File(args[0]));
V = src.nextInt();
D = src.nextInt();
} else {
V = io.nextInt();
D = io.nextInt();
}
assert 1 <= V && V <= 1000;
assert 1 <= D && D <= 640000;
boolean[][] E = io.nextBoolean('1', V);
for (boolean[] i : E) assert i.length == V;
assert !io.hasNext();
if (checkEdge) {
int cnt = 0;
for (boolean[] i : E) for (boolean j : i) if (j) ++ cnt;
assert D == 1 ? cnt == V * V : cnt == 2 * V - 1;
}
BitSet[] graph = new BitSet[V]; // 隣接頂点集合
for (int i = 0;i < V;++ i) {
graph[i] = new BitSet(V);
for (int j = 0;j < V;++ j) graph[i].set(j, E[i][j]);
}
boolean ans = graph[0].cardinality() > 0;
for (int i = 0;i < V;++ i) { // この頂点を始点として、全頂点にD回以内に行けるか判定
BitSet now = (BitSet)graph[i].clone(), one = new BitSet(V), two = new BitSet(V), three = new BitSet(V);
one.set(i);
for (int j = 1;j < D;++ j) {
BitSet check = (BitSet)now.clone();
check.xor(two);
if (check.isEmpty()) break; // もう更新されない
two = (BitSet)one.clone();
for (int k = check.nextSetBit(0);k >= 0;k = check.nextSetBit(k + 1)) one.or(graph[k]);
three = now;
now = one;
one = three;
}
ans &= now.cardinality() == V;
}
if (ans) io.println("Yes");
else io.println(":(");
if (checkEdge) assert ans;
}
public static void main(String[] args) {
new Main(args);
}
public Main(String[] args) {
io = new FastIO();
if (DEBUG) io.println("debug mode");
solve(io, args);
io.flush();
}
// 以下、ライブラリ
/**
* 高速な入出力を提供します。
* @author 31536000
*
*/
public static class FastIO {
private InputStream in;
private final byte[] buffer = new byte[1024];
private int read = 0;
private int length = 0;
private PrintWriter out;
private PrintWriter err;
private boolean autoFlush = false;
public FastIO() {
this(System.in, System.out, System.err);
}
public FastIO(InputStream in, PrintStream out, PrintStream err) {
this.in = in;
this.out = new PrintWriter(out, false);
this.err = new PrintWriter(err, false);
}
public final void setInputStream(InputStream in) {
this.in = in;
}
public final void setInputStream(File in) {
try {
this.in = new FileInputStream(in);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public final void setOutputStream(PrintStream out) {
this.out = new PrintWriter(out, false);
}
public final void setOutputStream(File out) {
try {
this.out = new PrintWriter(new FileOutputStream(out), false);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public final void setErrorStream(PrintStream err) {
this.err = new PrintWriter(err, false);
}
public final void setErrorStream(File err) {
try {
this.err = new PrintWriter(new FileOutputStream(err), false);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public final void setAutoFlush(boolean flush) {
autoFlush = flush;
}
private boolean hasNextByte() {
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return length > 0;
}
private int readByte() {
return hasNextByte() ? buffer[read++] : -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private static boolean isNumber(int c) {
return '0' <= c && c <= '9';
}
public final boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[read])) read++;
return hasNextByte();
}
public final char nextChar() {
if (!hasNextByte()) throw new NoSuchElementException();
return (char)readByte();
}
public final char[][] nextChar(int height) {
char[][] ret = new char[height][];
for (int i = 0;i < ret.length;++ i) ret[i] = next().toCharArray();
return ret;
}
public final String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b;
while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
return sb.toString();
}
public final String nextLine() {
StringBuilder sb = new StringBuilder();
int b;
while(!isPrintableChar(b = readByte()));
do sb.appendCodePoint(b); while(isPrintableChar(b = readByte()) || b == ' ');
return sb.toString();
}
public final long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (!isNumber(b)) throw new NumberFormatException();
while (true) {
if (isNumber(b)) {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n;
else throw new NumberFormatException();
b = readByte();
}
}
public final int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public final double nextDouble() {
return Double.parseDouble(next());
}
public final int[] nextInt(int width) {
int[] ret = new int[width];
for (int i = 0;i < width;++ i) ret[i] = nextInt();
return ret;
}
public final int[] nextInts() {
return nextInts(" ");
}
public final int[] nextInts(String parse) {
String[] get = nextLine().split(parse);
int[] ret = new int[get.length];
for (int i = 0;i < ret.length;++ i) ret[i] = Integer.valueOf(get[i]);
return ret;
}
public final long[] nextLong(int width) {
long[] ret = new long[width];
for (int i = 0;i < width;++ i) ret[i] = nextLong();
return ret;
}
public final long[] nextLongs() {
return nextLongs(" ");
}
public final long[] nextLongs(String parse) {
String[] get = nextLine().split(parse);
long[] ret = new long[get.length];
for (int i = 0;i < ret.length;++ i) ret[i] = Long.valueOf(get[i]);
return ret;
}
public final int[][] nextInt(int width, int height) {
int[][] ret = new int[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[i][j] = nextInt();
return ret;
}
public final long[][] nextLong(int width, int height) {
long[][] ret = new long[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
return ret;
}
public final boolean[] nextBoolean(char T) {
char[] s = next().toCharArray();
boolean[] ret = new boolean[s.length];
for (int i = 0;i < ret.length;++ i) ret[i] = s[i] == T;
return ret;
}
public final boolean[][] nextBoolean(char T, int height) {
boolean[][] ret = new boolean[height][];
for (int i = 0;i < ret.length;++ i) {
char[] s = next().toCharArray();
ret[i] = new boolean[s.length];
for (int j = 0;j < ret[i].length;++ j) ret[i][j] = s[j] == T;
}
return ret;
}
public final Point nextPoint() {
return new Point(nextInt(), nextInt());
}
public final Point[] nextPoint(int width) {
Point[] ret = new Point[width];
for (int i = 0;i < width;++ i) ret[i] = nextPoint();
return ret;
}
@Override
protected void finalize() throws Throwable {
try {
super.finalize();
} finally {
in.close();
out.close();
err.close();
}
}
public final boolean print(boolean b) {
out.print(b);
if (autoFlush) flush();
return b;
}
public final Object print(boolean b, Object t, Object f) {
return b ? print(t) : print(f);
}
public final char print(char c) {
out.print(c);
if (autoFlush) flush();
return c;
}
public final char[] print(char[] s) {
out.print(s);
return s;
}
public final double print(double d) {
out.print(d);
if (autoFlush) flush();
return d;
}
public final double print(double d, int length) {
if (d < 0) {
out.print('-');
d = -d;
}
d += Math.pow(10, -length) / 2;
out.print((long)d);
out.print('.');
d -= (long)d;
for (int i = 0;i < length;++ i) {
d *= 10;
out.print((int)d);
d -= (int)d;
}
if (autoFlush) flush();
return d;
}
public final float print(float f) {
out.print(f);
if (autoFlush) flush();
return f;
}
public final int print(int i) {
out.print(i);
if (autoFlush) flush();
return i;
}
public final long print(long l) {
out.print(l);
if (autoFlush) flush();
return l;
}
public final Object print(Object obj) {
if (obj.getClass().isArray()) {
if (obj instanceof boolean[][]) print(obj, "\n", " ");
else if (obj instanceof byte[][]) print(obj, "\n", " ");
else if (obj instanceof short[][]) print(obj, "\n", " ");
else if (obj instanceof int[][]) print(obj, "\n", " ");
else if (obj instanceof long[][]) print(obj, "\n", " ");
else if (obj instanceof float[][]) print(obj, "\n", " ");
else if (obj instanceof double[][]) print(obj, "\n", " ");
else if (obj instanceof char[][]) print(obj, "\n", " ");
else if (obj instanceof Object[][]) print(obj, "\n", " ");
else print(obj, " ");
} else {
out.print(obj);
if (autoFlush) flush();
}
return obj;
}
public final String print(String s) {
out.print(s);
if (autoFlush) flush();
return s;
}
public final Object print(Object array, String... parse) {
print(array, 0, parse);
if (autoFlush) flush();
return array;
}
private final Object print(Object array, int check, String... parse) {
if (check >= parse.length) {
if (array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
print(array);
return array;
}
String str = parse[check];
if (array instanceof Object[]) {
Object[] obj = (Object[]) array;
if (obj.length == 0) return array;
print(obj[0], check + 1, parse);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i], check + 1, parse);
}
return array;
}
if (array instanceof Collection) {
Iterator<?> iter = ((Collection<?>)array).iterator();
if (!iter.hasNext()) return array;
print(iter.next(), check + 1, parse);
while(iter.hasNext()) {
print(str);
print(iter.next(), check + 1, parse);
}
return array;
}
if (!array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
if (check != parse.length - 1) throw new IllegalArgumentException("not equal dimension");
if (array instanceof boolean[]) {
boolean[] obj = (boolean[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof byte[]) {
byte[] obj = (byte[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
return array;
} else if (array instanceof short[]) {
short[] obj = (short[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof int[]) {
int[] obj = (int[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof long[]) {
long[] obj = (long[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof float[]) {
float[] obj = (float[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof double[]) {
double[] obj = (double[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof char[]) {
char[] obj = (char[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else throw new AssertionError();
return array;
}
public final Object[] print(String parse, Object... args) {
print(args[0]);
for (int i = 1;i < args.length;++ i) {
print(parse);
print(args[i]);
}
return args;
}
public final Object[] printf(String format, Object... args) {
out.printf(format, args);
if (autoFlush) flush();
return args;
}
public final Object printf(Locale l, String format, Object... args) {
out.printf(l, format, args);
if (autoFlush) flush();
return args;
}
public final void println() {
out.println();
if (autoFlush) flush();
}
public final boolean println(boolean b) {
out.println(b);
if (autoFlush) flush();
return b;
}
public final Object println(boolean b, Object t, Object f) {
return b ? println(t) : println(f);
}
public final char println(char c) {
out.println(c);
if (autoFlush) flush();
return c;
}
public final char[] println(char[] s) {
out.println(s);
if (autoFlush) flush();
return s;
}
public final double println(double d) {
out.println(d);
if (autoFlush) flush();
return d;
}
public final double println(double d, int length) {
print(d, length);
println();
return d;
}
public final float println(float f) {
out.println(f);
if (autoFlush) flush();
return f;
}
public final int println(int i) {
out.println(i);
if (autoFlush) flush();
return i;
}
public final long println(long l) {
out.println(l);
if (autoFlush) flush();
return l;
}
public final Object println(Object obj) {
print(obj);
println();
return obj;
}
public final String println(String s) {
out.println(s);
if (autoFlush) flush();
return s;
}
public final Object println(Object array, String... parse) {
print(array, parse);
println();
return array;
}
public final boolean debug(boolean b) {
err.print(b);
if (autoFlush) flush();
return b;
}
public final Object debug(boolean b, Object t, Object f) {
return b ? debug(t) : debug(f);
}
public final char debug(char c) {
err.print(c);
if (autoFlush) flush();
return c;
}
public final char[] debug(char[] s) {
err.print(s);
return s;
}
public final double debug(double d) {
err.print(d);
if (autoFlush) flush();
return d;
}
public final double debug(double d, int length) {
if (d < 0) {
err.print('-');
d = -d;
}
d += Math.pow(10, -length) / 2;
err.print((long)d);
err.print('.');
d -= (long)d;
for (int i = 0;i < length;++ i) {
d *= 10;
err.print((int)d);
d -= (int)d;
}
if (autoFlush) flush();
return d;
}
public final float debug(float f) {
err.print(f);
if (autoFlush) flush();
return f;
}
public final int debug(int i) {
err.print(i);
if (autoFlush) flush();
return i;
}
public final long debug(long l) {
err.print(l);
if (autoFlush) flush();
return l;
}
public final Object debug(Object obj) {
if (obj.getClass().isArray()) {
if (obj instanceof boolean[][]) debug(obj, "\n", " ");
else if (obj instanceof byte[][]) debug(obj, "\n", " ");
else if (obj instanceof short[][]) debug(obj, "\n", " ");
else if (obj instanceof int[][]) debug(obj, "\n", " ");
else if (obj instanceof long[][]) debug(obj, "\n", " ");
else if (obj instanceof float[][]) debug(obj, "\n", " ");
else if (obj instanceof double[][]) debug(obj, "\n", " ");
else if (obj instanceof char[][]) debug(obj, "\n", " ");
else if (obj instanceof Object[][]) debug(obj, "\n", " ");
else debug(obj, " ");
} else {
err.print(obj);
if (autoFlush) flush();
}
return obj;
}
public final String debug(String s) {
err.print(s);
if (autoFlush) flush();
return s;
}
public final Object debug(Object array, String... parse) {
debug(array, 0, parse);
if (autoFlush) flush();
return array;
}
private final Object debug(Object array, int check, String... parse) {
if (check >= parse.length) {
if (array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
debug(array);
return array;
}
String str = parse[check];
if (array instanceof Object[]) {
Object[] obj = (Object[]) array;
if (obj.length == 0) return array;
debug(obj[0], check + 1, parse);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i], check + 1, parse);
}
return array;
}
if (array instanceof Collection) {
Iterator<?> iter = ((Collection<?>)array).iterator();
if (!iter.hasNext()) return array;
debug(iter.next(), check + 1, parse);
while(iter.hasNext()) {
debug(str);
debug(iter.next(), check + 1, parse);
}
return array;
}
if (!array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
if (check != parse.length - 1) throw new IllegalArgumentException("not equal dimension");
if (array instanceof boolean[]) {
boolean[] obj = (boolean[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof byte[]) {
byte[] obj = (byte[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
return array;
} else if (array instanceof short[]) {
short[] obj = (short[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof int[]) {
int[] obj = (int[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof long[]) {
long[] obj = (long[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof float[]) {
float[] obj = (float[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof double[]) {
double[] obj = (double[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else if (array instanceof char[]) {
char[] obj = (char[]) array;
if (obj.length == 0) return array;
debug(obj[0]);
for (int i = 1;i < obj.length;++ i) {
debug(str);
debug(obj[i]);
}
} else throw new AssertionError();
return array;
}
public final Object[] debug(String parse, Object... args) {
debug(args[0]);
for (int i = 1;i < args.length;++ i) {
debug(parse);
debug(args[i]);
}
return args;
}
public final Object[] debugf(String format, Object... args) {
err.printf(format, args);
if (autoFlush) flush();
return args;
}
public final Object debugf(Locale l, String format, Object... args) {
err.printf(l, format, args);
if (autoFlush) flush();
return args;
}
public final void debugln() {
err.println();
if (autoFlush) flush();
}
public final boolean debugln(boolean b) {
err.println(b);
if (autoFlush) flush();
return b;
}
public final Object debugln(boolean b, Object t, Object f) {
return b ? debugln(t) : debugln(f);
}
public final char debugln(char c) {
err.println(c);
if (autoFlush) flush();
return c;
}
public final char[] debugln(char[] s) {
err.println(s);
if (autoFlush) flush();
return s;
}
public final double debugln(double d) {
err.println(d);
if (autoFlush) flush();
return d;
}
public final double debugln(double d, int length) {
debug(d, length);
debugln();
return d;
}
public final float debugln(float f) {
err.println(f);
if (autoFlush) flush();
return f;
}
public final int debugln(int i) {
err.println(i);
if (autoFlush) flush();
return i;
}
public final long debugln(long l) {
err.println(l);
if (autoFlush) flush();
return l;
}
public final Object debugln(Object obj) {
debug(obj);
debugln();
return obj;
}
public final String debugln(String s) {
err.println(s);
if (autoFlush) flush();
return s;
}
public final Object debugln(Object array, String... parse) {
debug(array, parse);
debugln();
return array;
}
public final void flush() {
out.flush();
err.flush();
}
}
public enum BoundType {
CLOSED, OPEN;
}
public static class Range<C> implements Serializable{
private static final long serialVersionUID = -4702828934863023392L;
protected C lower;
protected C upper;
protected BoundType lowerType;
protected BoundType upperType;
private Comparator<? super C> comparator;
protected Range(C lower, BoundType lowerType, C upper, BoundType upperType) {
this(lower, lowerType, upper, upperType, null);
}
protected Range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
this.lower = lower;
this.upper = upper;
this.lowerType = lowerType;
this.upperType = upperType;
this.comparator = comparator;
}
public static <C extends Comparable<? super C>> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType) {
if (lower != null && upper != null) {
int comp = lower.compareTo(upper);
if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN))return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
}
return new Range<C>(lower, lowerType, upper, upperType);
}
public static <C> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
if (lower != null && upper != null) {
int comp = comparator.compare(lower, upper);
if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
}
return new Range<C>(lower, lowerType, upper, upperType, comparator);
}
public static <C extends Comparable<? super C>> Range<C> all() {
return range((C)null, BoundType.OPEN, null, BoundType.OPEN);
}
public static <C> Range<C> all(Comparator<? super C> comparator) {
return range((C)null, BoundType.OPEN, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> atMost(C upper) {
return range(null, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static <C> Range<C> atMost(C upper, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> lessThan(C upper) {
return range(null, BoundType.OPEN, upper, BoundType.OPEN);
}
public static <C> Range<C> lessThan(C upper, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> downTo(C upper, BoundType boundType) {
return range(null, BoundType.OPEN, upper, boundType);
}
public static <C> Range<C> downTo(C upper, BoundType boundType, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, boundType, comparator);
}
public static <C extends Comparable<? super C>> Range<C> atLeast(C lower) {
return range(lower, BoundType.CLOSED, null, BoundType.OPEN);
}
public static <C> Range<C> atLeast(C lower, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> greaterThan(C lower) {
return range(lower, BoundType.OPEN, null, BoundType.OPEN);
}
public static <C> Range<C> greaterThan(C lower, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> upTo(C lower, BoundType boundType) {
return range(lower, boundType, null, BoundType.OPEN);
}
public static <C> Range<C> upTo(C lower, BoundType boundType, Comparator<? super C> comparator) {
return range(lower, boundType, null, BoundType.OPEN, comparator );
}
public static <C extends Comparable<? super C>> Range<C> open(C lower, C upper) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
}
public static <C> Range<C> open(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> openClosed(C lower, C upper) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static <C> Range<C> openClosed(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> closedOpen(C lower, C upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static <C> Range<C> closedOpen(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> closed(C lower, C upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static <C> Range<C> closed(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> singleton(C value) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
}
public static <C> Range<C> singleton(C value, Comparator<? super C> comparator) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> empty() {
return range((C)null, BoundType.CLOSED, null, BoundType.CLOSED);
}
public static <C> Range<C> empty(Comparator<? super C> comparator) {
return range((C)null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> encloseAll(Iterable<C> values) {
C lower = values.iterator().next();
C upper = lower;
for (C i : values) {
if (lower.compareTo(i) > 0) lower = i;
if (upper.compareTo(i) < 0) upper = i;
}
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static <C> Range<C> encloseAll(Iterable<C> values, Comparator<? super C> comparator) {
C lower = values.iterator().next();
C upper = lower;
for (C i : values) {
if (comparator.compare(lower, i) > 0) lower = i;
if (comparator.compare(upper, i) < 0) upper = i;
}
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
}
protected int compareLower(C value) {
return compareLower(value, BoundType.CLOSED);
}
protected int compareLower(C value, BoundType boundType) {
return compareLower(lower, lowerType, value, boundType);
}
protected int compareLower(C lower, BoundType lowerType, C value) {
return compareLower(lower, lowerType, value, BoundType.CLOSED);
}
protected int compareLower(C lower, BoundType lowerType, C value, BoundType boundType) {
if (lower == null) return value == null ? 0 : -1;
else if (value == null) return 1;
int compare;
if (comparator == null) {
@SuppressWarnings("unchecked")
Comparable<C> comp = (Comparable<C>)lower;
compare = comp.compareTo(value);
} else compare = comparator.compare(lower, value);
if (compare == 0) {
if (lowerType == BoundType.CLOSED) -- compare;
if (boundType == BoundType.CLOSED) ++ compare;
}
return compare;
}
protected int compareUpper(C value) {
return compareUpper(value, BoundType.CLOSED);
}
protected int compareUpper(C value, BoundType boundType) {
return compareUpper(upper, upperType, value, boundType);
}
protected int compareUpper(C upper, BoundType upperType, C value) {
return compareUpper(upper, upperType, value, BoundType.CLOSED);
}
protected int compareUpper(C upper, BoundType upperType, C value, BoundType boundType) {
if (upper == null) return value == null ? 0 : 1;
if (value == null) return -1;
int compare;
if (comparator == null) {
@SuppressWarnings("unchecked")
Comparable<C> comp = (Comparable<C>)upper;
compare = comp.compareTo(value);
} else compare = comparator.compare(upper, value);
if (compare == 0) {
if (upperType == BoundType.CLOSED) ++ compare;
if (boundType == BoundType.CLOSED) -- compare;
}
return compare;
}
public boolean hasLowerBound() {
return lower != null;
}
public C lowerEndpoint() {
if (hasLowerBound()) return lower;
throw new IllegalStateException();
}
public BoundType lowerBoundType() {
if (hasLowerBound()) return lowerType;
throw new IllegalStateException();
}
public boolean hasUpperBound() {
return upper != null;
}
public C upperEndpoint() {
if (hasUpperBound()) return upper;
throw new IllegalStateException();
}
public BoundType upperBoundType() {
if (hasUpperBound()) return upperType;
throw new IllegalStateException();
}
/**
* この区間が空集合か判定します。
* @return 空集合ならばtrue
*/
public boolean isEmpty() {
return lower == null && upper == null && lowerType == BoundType.CLOSED;
}
/**
* 与えられた引数が区間の左側に位置するか判定します。<br>
* 接する場合は区間の左側ではないと判定します。
* @param value 調べる引数
* @return 区間の左側に位置するならtrue
*/
public boolean isLess(C value) {
return isLess(value, BoundType.CLOSED);
}
protected boolean isLess(C value, BoundType boundType) {
return compareLower(value, boundType) > 0;
}
/**
* 与えられた引数が区間の右側に位置するか判定します。<br>
* 接する場合は区間の右側ではないと判定します。
* @param value 調べる引数
* @return 区間の右側に位置するならtrue
*/
public boolean isGreater(C value) {
return isGreater(value, BoundType.CLOSED);
}
private boolean isGreater(C value, BoundType boundType) {
return compareUpper(value, boundType) < 0;
}
/**
* 与えられた引数が区間内に位置するか判定します。<br>
* 接する場合も区間内に位置すると判定します。
* @param value 調べる引数
* @return 区間内に位置するならtrue
*/
public boolean contains(C value) {
return !isLess(value) && !isGreater(value) && !isEmpty();
}
/**
* 与えられた引数すべてが区間内に位置するか判定します。<br>
* 接する場合も区間内に位置すると判定します。
* @param value 調べる要素
* @return 全ての要素が区間内に位置するならtrue
*/
public boolean containsAll(Iterable<? extends C> values) {
for (C i : values) if (!contains(i)) return false;
return true;
}
/**
* 与えられた区間がこの区間に内包されるか判定します。<br>
*
* @param other
* @return 与えられた区間がこの区間に内包されるならtrue
*/
public boolean encloses(Range<C> other) {
return !isLess(other.lower, other.lowerType) && !isGreater(other.upper, other.upperType);
}
/**
* 与えられた区間がこの区間と公差するか判定します。<br>
* 接する場合は公差するものとします。
* @param value 調べる引数
* @return 区間が交差するならtrue
*/
public boolean isConnected(Range<C> other) {
if (this.isEmpty() || other.isEmpty()) return false;
C lower, upper;
BoundType lowerType, upperType;
if (isLess(other.lower, other.lowerType)) {
lower = other.lower;
lowerType = other.lowerType;
} else {
lower = this.lower;
lowerType = this.lowerType;
}
if (isGreater(other.upper, other.upperType)) {
upper = other.upper;
upperType = other.upperType;
} else {
upper = this.upper;
upperType = this.upperType;
}
if (lower == null || upper == null) return true;
int comp = compareLower(lower, lowerType, upper, upperType);
return comp <= 0;
}
/**
* この区間との積集合を返します。
* @param connectedRange 積集合を求める区間
* @return 積集合
*/
public Range<C> intersection(Range<C> connectedRange) {
if (this.isEmpty() || connectedRange.isEmpty()) {
if (comparator == null) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
return empty(comparator);
}
C lower, upper;
BoundType lowerType, upperType;
if (isLess(connectedRange.lower, connectedRange.lowerType)) {
lower = connectedRange.lower;
lowerType = connectedRange.lowerType;
} else {
lower = this.lower;
lowerType = this.lowerType;
}
if (isGreater(connectedRange.upper, connectedRange.upperType)) {
upper = connectedRange.upper;
upperType = connectedRange.upperType;
} else {
upper = this.upper;
upperType = this.upperType;
}
if (comparator == null) {
return new Range<C>(lower, lowerType, upper, upperType);
}
return range(lower, lowerType, upper, upperType, comparator);
}
/**
* この区間との和集合を返します。
* @param other 和集合を求める区間
* @return 和集合
*/
public Range<C> span(Range<C> other) {
if (other.isEmpty()) return new Range<C>(lower, lowerType, upper, upperType);
C lower, upper;
BoundType lowerType, upperType;
if (isLess(other.lower, other.lowerType)) {
lower = this.lower;
lowerType = this.lowerType;
} else {
lower = other.lower;
lowerType = other.lowerType;
}
if (isGreater(other.upper, other.upperType)) {
upper = this.upper;
upperType = this.upperType;
} else {
upper = other.upper;
upperType = other.upperType;
}
return new Range<C>(lower, lowerType, upper, upperType, comparator);
}
@Override
public boolean equals(Object object) {
if (this == object) return true;
if (object instanceof Range) {
@SuppressWarnings("unchecked")
Range<C> comp = (Range<C>) object;
return compareLower(comp.lower, comp.lowerType) == 0 && compareUpper(comp.upper, comp.upperType) == 0 && lowerType == comp.lowerType && upperType == comp.upperType;
}
return false;
}
@Override
public int hashCode() {
if (lower == null && upper == null) return 0;
else if (lower == null) return upper.hashCode();
else if (upper == null) return lower.hashCode();
return lower.hashCode() ^ upper.hashCode();
}
@Override
public String toString() {
if (isEmpty()) return "()";
return (lowerType == BoundType.OPEN ? "(" : "[") + (lower == null ? "" : lower.toString()) + ".." + (upper == null ? "" : upper.toString()) + (upperType == BoundType.OPEN ? ")" : "]");
}
}
public static class IterableRange<C> extends Range<C> implements Iterable<C>{
private static final long serialVersionUID = 9065915259748260688L;
protected UnaryOperator<C> func;
protected IterableRange(C lower, BoundType lowerType, C upper, BoundType upperType, UnaryOperator<C> func) {
super(lower, lowerType, upper, upperType);
this.func = func;
}
public static <C extends Comparable<? super C>> IterableRange<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, UnaryOperator<C> func) {
if (lower == null || upper == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
int comp = lower.compareTo(upper);
if (comp > 0) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return new IterableRange<C>(lower, lowerType, upper, upperType, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> open(C lower, C upper, UnaryOperator<C> func) {
if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return range(func.apply(lower), BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> openClosed(C lower, C upper, UnaryOperator<C> func) {
if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return range(func.apply(lower), BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> closedOpen(C lower, C upper, UnaryOperator<C> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> closed(C lower, C upper, UnaryOperator<C> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> singleton(C value, UnaryOperator<C> func) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func);
}
protected class Iter implements Iterator<C> {
C now;
Iter() {
now = lower;
}
@Override
public final boolean hasNext() {
return !isGreater(now);
}
@Override
public final C next() {
C ret = now;
now = func.apply(now);
return ret;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
protected class EmptyIter implements Iterator<C> {
@Override
public boolean hasNext() {
return false;
}
@Override
public C next() {
return null;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<C> iterator() {
return lower == null || upper == null ? new EmptyIter() : new Iter();
}
public int getDistance() {
C check = upper;
int ret = 0;
while (lower != check) {
check = func.apply(check);
++ ret;
}
return ret;
}
}
public static class IntRange extends IterableRange<Integer>{
private static final long serialVersionUID = 5623995336491967216L;
private final boolean useFastIter;
private static class Next implements UnaryOperator<Integer> {
@Override
public Integer apply(Integer value) {
return value + 1;
}
}
protected IntRange() {
super(null, BoundType.CLOSED, null, BoundType.CLOSED, new Next());
useFastIter = true;
}
protected IntRange(UnaryOperator<Integer> func) {
super(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
useFastIter = false;
}
protected IntRange(int lower, BoundType lowerType, int upper, BoundType upperType) {
super(lower, lowerType, upper, upperType, new Next());
useFastIter = true;
}
protected IntRange(int lower, BoundType lowerType, int upper, BoundType upperType, UnaryOperator<Integer> func) {
super(lower, lowerType, upper, upperType, func);
useFastIter = false;
}
public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType) {
if (lower > upper) return new IntRange();
if (lowerType == BoundType.OPEN) ++ lower;
if (upperType == BoundType.OPEN) -- upper;
return new IntRange(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType, UnaryOperator<Integer> func) {
if (lower > upper) return new IntRange(func);
if (lowerType == BoundType.OPEN) ++ lower;
if (upperType == BoundType.OPEN) -- upper;
return new IntRange(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static IntRange open(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
}
public static IntRange open(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN, func);
}
public static IntRange open(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange open(int upper, UnaryOperator<Integer> func) {
return range(0, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static IntRange openClosed(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static IntRange openClosed(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, func);
}
public static IntRange closedOpen(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange closedOpen(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static IntRange closed(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange closed(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static IntRange closed(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange closed(int upper, UnaryOperator<Integer> func) {
return range(0, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static IntRange singleton(int value) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
}
public static IntRange singleton(int value, UnaryOperator<Integer> func) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func);
}
private class FastIter implements Iterator<Integer> {
int now;
public FastIter() {
now = lower;
}
@Override
public final boolean hasNext() {
return now <= upper;
}
@Override
public final Integer next() {
return now++;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
private class Iter implements Iterator<Integer> {
int now;
public Iter() {
now = lower;
}
@Override
public final boolean hasNext() {
return now <= upper;
}
@Override
public final Integer next() {
int ret = now;
now = func.apply(now);
return ret;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<Integer> iterator() {
return lower == null || upper == null ? new EmptyIter() : useFastIter ? new FastIter() : new Iter();
}
@Override
public int getDistance() {
int ret = upper - lower;
if (upperType == BoundType.CLOSED) ++ ret;
return ret;
}
public int getClosedLower() {
return lower;
}
public int getOpenLower() {
return lower - 1;
}
public int getClosedUpper() {
return upperType == BoundType.CLOSED ? upper : upper - 1;
}
public int getOpenUpper() {
return upperType == BoundType.CLOSED ? upper + 1 : upper;
}
}
}