結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2016-02-24 02:16:14 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 14,182 bytes |
コンパイル時間 | 3,220 ms |
コンパイル使用メモリ | 93,560 KB |
実行使用メモリ | 50,692 KB |
最終ジャッジ日時 | 2024-09-22 13:16:42 |
合計ジャッジ時間 | 6,069 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.IOException;import java.io.InputStreamReader;import java.util.BitSet;import java.util.Random;public class Main {/*** This class represents a problem setting.*/class Problem implements IProblem {int N;int[] D, W;@Overridepublic void set(ProblemReader reader) throws IOException {N = reader.nextInt();D = reader.nextIntArray();W = reader.nextIntArray();}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append(StringUtils.toString(N) + "\n");sb.append(StringUtils.toString(D) + "\n");sb.append(StringUtils.toString(W));return sb.toString();}}/*** Solver for the problem.* It's the most important part of codes in this file.*/class Solver implements IProblemSolver<Problem> {@Overridepublic String solve(Problem problem) {int N = problem.N;int[] D = problem.D;int[] W = problem.W;return solve(N, D, W) ? "Yes" : "No";}private boolean solve(int N, int[] D, int[] W) {BitSet[] bitsets = new BitSet[N];for (int i = 0; i < N; i++) {bitsets[i] = new BitSet();}for (int i = 0; i < N; i++) {int l = i - D[i];if (l < 0) {l += ((-l - 1) / N + 1) * N;}int r = (i + D[i]) % N;bitsets[l].set(i);bitsets[r].set(i);if (W[i] == 0) {bitsets[i].set(N);}}int idx = 0;for (int i = 0; i < N; i++) {int pivot = -1;for (int j = idx; j < N; j++) {if (bitsets[j].get(i)) {pivot = j;break;}}if (pivot >= 0) {BitSet tmp = bitsets[idx]; bitsets[idx] = bitsets[pivot]; bitsets[pivot] = tmp;for (int j = 0; j < N; j++) {if (j != idx && bitsets[j].get(i)) {bitsets[j].xor(bitsets[idx]);}}idx++;}}for (int i = idx; i < N; i++) {if (bitsets[i].get(N)) {return false;}}return true;}}/*** This class is a solver to confirm the main solver.* This solver often works only for a problem with a small number setting.*/class Solver2 implements IProblemSolver<Problem> {@Overridepublic String solve(Problem problem) {int N = problem.N;int[] D = problem.D;int[] W = problem.W;return solve(N, D, W) ? "Yes" : "No";}private boolean solve(int N, int[] D, int[] W) {UnionFindTree uft = new UnionFindTree(N);boolean[] isSingle = new boolean[N];for (int i = 0; i < N; i++) {int l = i - D[i];if (l < 0) {l += ((-l - 1) / N + 1) * N;}int r = (i + D[i]) % N;if (l == r) {isSingle[l] = true;} else {uft.unite(l, r);}}boolean[] checked = new boolean[N];for (int i = 0; i < N; i++) {if (checked[i]) {continue;}int cnt = 0;boolean possible = false;for (int j = i; j < N; j++) {if (uft.same(i, j)) {checked[j] = true;if (isSingle[j]) {possible = true;break;} else if (W[j] == 0) {cnt++;}}}if (!possible && cnt % 2 != 0) {return false;}}return true;}class UnionFindTree {int[] parent;int[] rank;UnionFindTree(int size) {parent = new int[size];rank = new int[size];init();}void init() {for (int i=0; i<parent.length; i++) {parent[i] = i;rank[i] = 0;}}int find(int x) {if (parent[x] == x) {return x;} else {return parent[x] = find(parent[x]);}}void unite(int x, int y) {x = find(x);y = find(y);if (x==y) {return;}if (rank[x] < rank[y]) {parent[x] = y;} else {parent[y] = x;if (rank[x] == rank[y]) {rank[x]++;}}}boolean same(int x, int y) {return find(x) == find(y);}}}class Factory implements IProblemFactory<Problem> {Random rng = new Random();@Overridepublic Problem newProblem() {Problem problem = new Problem();problem.N = 10;problem.D = new int[problem.N];problem.W = new int[problem.N];for (int i = 0; i < problem.N; i++) {problem.D[i] = rng.nextInt(1000) + 1;problem.W[i] = rng.nextBoolean() ? 1 : 0;}return problem;}@Overridepublic Problem newProblem(ProblemReader reader) throws IOException {Problem problem = new Problem();problem.set(reader);return problem;}}ProblemProcessor<Problem> processor;Main() {Init();}void Init() {ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();config.factory = new Factory();config.solver = new Solver();config.solver2 = new Solver2();processor = new ProblemProcessor<Problem>(config);}void process(String mode) throws IOException {processor.process(mode);}public static void main(String args[]) throws IOException {String mode = "solve";new Main().process(mode);}/*Common library*/interface IProblem {abstract void set(ProblemReader reader) throws IOException;}interface IProblemFactory<P extends IProblem> {abstract P newProblem();abstract P newProblem(ProblemReader reader) throws IOException;}interface IProblemSolver<P extends IProblem> {abstract String solve(P problem);}class ProblemReader {BufferedReader br = null;ProblemReader() {br = new BufferedReader(new InputStreamReader(System.in));}int nextInt() throws IOException {return StringUtils.toInt(br.readLine());}long nextLong() throws IOException {return StringUtils.toLong(br.readLine());}double nextDouble() throws IOException {return StringUtils.toDouble(br.readLine());}String nextString() throws IOException {return br.readLine();}int[] nextIntArray() throws IOException {return StringUtils.toIntArray(br.readLine());}long[] nextLongArray() throws IOException {return StringUtils.toLongArray(br.readLine());}double[] nextDoubleArray() throws IOException {return StringUtils.toDoubleArray(br.readLine());}String[] nextStringArray() throws IOException {return StringUtils.toStringArray(br.readLine());}int[] nextIntArray(int n) throws IOException {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = nextInt();}return a;}long[] nextLongArray(int n) throws IOException {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nextLong();}return a;}double[] nextDoubleArray(int n) throws IOException {double[] a = new double[n];for (int i = 0; i < n; i++) {a[i] = nextDouble();}return a;}String[] nextStringArray(int n) throws IOException {String[] strs = new String[n];for (int i = 0; i < n; i++) {strs[i] = nextString();}return strs;}int[][] nextIntArray2(int n) throws IOException {int[][] a = new int[n][];for (int i = 0; i < n; i++) {a[i] = nextIntArray();}return a;}long[][] nextLongArray2(int n) throws IOException {long[][] a = new long[n][];for (int i = 0; i < n; i++) {a[i] = nextLongArray();}return a;}double[][] nextDoubleArray2(int n) throws IOException {double[][] a = new double[n][];for (int i = 0; i < n; i++) {a[i] = nextDoubleArray();}return a;}String[][] nextStringArray2(int n) throws IOException {String[][] strs = new String[n][];for (int i = 0; i < n; i++) {strs[i] = nextStringArray();}return strs;}void close() throws IOException {if (br != null) {br.close();}}}class ProblemCreator<P extends IProblem> {IProblemFactory<P> factory;ProblemCreator(IProblemFactory<P> factory) {this.factory = factory;}void create() throws FileNotFoundException {P problem = factory.newProblem();System.out.println(problem.toString());}}class ProblemSolverComparator<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver1, solver2;ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2) {this.factory = factory;this.solver1 = solver1;this.solver2 = solver2;}void compare() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res1 = solver1.solve(problem);String res2 = solver2.solve(problem);if (res1.equals(res2)) {System.out.println(res1);} else {System.err.println(res1 + " " + res2);}} finally {if (reader != null) {reader.close();}}}}class ProblemAnswerer<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver;ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {this.factory = factory;this.solver = solver;}void answer() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res = solver.solve(problem);System.out.println(res);} finally {if (reader != null) {reader.close();}}}}class ProblemProcessorConfig<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver, solver2;}class ProblemProcessor<P extends IProblem> {ProblemProcessorConfig<P> config;ProblemCreator<P> creator;ProblemSolverComparator<P> comparator;ProblemAnswerer<P> answerer;ProblemProcessor(ProblemProcessorConfig<P> config) {this.config = config;creator = new ProblemCreator<P>(config.factory);comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2);answerer = new ProblemAnswerer<P>(config.factory, config.solver);}void process(String mode) throws IOException {switch (mode) {case "create":creator.create();break;case "debug":comparator.compare();break;case "solve":answerer.answer();break;}}}static class StringUtils {static String toString(int a) {return String.valueOf(a);}static String toString(long a) {return String.valueOf(a);}static String toString(double a) {return String.valueOf(a);}static String toString(String str) {return str;}static String toString(int[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(long[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(double[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(String[] strs) {StringBuilder sb = new StringBuilder();for (int i = 0; i < strs.length; i++) {if (i < strs.length - 1) {sb.append(strs[i] + " ");} else {sb.append(strs[i]);}}return sb.toString();}static String toString(int[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(long[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(double[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(String[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static int toInt(String s) throws IOException {return Integer.parseInt(s);}static long toLong(String s) throws IOException {return Long.parseLong(s);}static double toDouble(String s) throws IOException {return Double.parseDouble(s);}static int[] toIntArray(String s) throws IOException {String[] tokens = s.split(" ");int[] a = new int[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Integer.parseInt(tokens[i]);}return a;}static long[] toLongArray(String s) throws IOException {String[] tokens = s.split(" ");long[] a = new long[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Long.parseLong(tokens[i]);}return a;}static double[] toDoubleArray(String s) throws IOException {String[] tokens = s.split(" ");double[] a = new double[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Double.parseDouble(tokens[i]);}return a;}static String[] toStringArray(String s) throws IOException {return s.split(" ");}}}