結果

問題 No.74 貯金箱の退屈
ユーザー atn112323atn112323
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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;
@Override
public void set(ProblemReader reader) throws IOException {
N = reader.nextInt();
D = reader.nextIntArray();
W = reader.nextIntArray();
}
@Override
public 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> {
@Override
public 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> {
@Override
public 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();
@Override
public 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;
}
@Override
public 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(" ");
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0