#680444 (Java21) No.1611 Minimum Multiple with Double Divisors

提出ソース
結果

問題	No.1611 Minimum Multiple with Double Divisors
ユーザー	CaliPota
提出日時	2021-07-21 22:24:48
言語	Java21 (openjdk 21)
結果	AC
実行時間	475 ms / 2,000 ms
コード長	29,475 bytes
コンパイル時間	3,723 ms
コンパイル使用メモリ	92,820 KB
実行使用メモリ	53,852 KB
最終ジャッジ日時	2024-10-03 02:32:52
合計ジャッジ時間	15,374 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	475 ms 52,152 KB
testcase_01	AC	426 ms 53,544 KB
testcase_02	AC	415 ms 53,852 KB
testcase_03	AC	424 ms 53,772 KB
testcase_04	AC	409 ms 53,528 KB
testcase_05	AC	409 ms 53,600 KB
testcase_06	AC	408 ms 53,264 KB
testcase_07	AC	397 ms 53,064 KB
testcase_08	AC	396 ms 53,372 KB
testcase_09	AC	399 ms 53,252 KB
testcase_10	AC	352 ms 51,520 KB
testcase_11	AC	347 ms 50,800 KB
testcase_12	AC	383 ms 52,140 KB
testcase_13	AC	342 ms 51,092 KB
testcase_14	AC	337 ms 52,144 KB
testcase_15	AC	341 ms 50,968 KB
testcase_16	AC	354 ms 52,508 KB
testcase_17	AC	335 ms 51,480 KB
testcase_18	AC	368 ms 52,644 KB
testcase_19	AC	76 ms 37,508 KB
testcase_20	AC	67 ms 37,536 KB
testcase_21	AC	69 ms 37,444 KB
testcase_22	AC	66 ms 37,208 KB
testcase_23	AC	67 ms 37,680 KB
testcase_24	AC	71 ms 37,608 KB
testcase_25	AC	66 ms 37,612 KB
testcase_26	AC	65 ms 37,676 KB
testcase_27	AC	77 ms 37,168 KB
testcase_28	AC	53 ms 37,240 KB
testcase_29	AC	53 ms 37,244 KB
testcase_30	AC	53 ms 37,096 KB
testcase_31	AC	53 ms 37,232 KB
testcase_32	AC	53 ms 37,248 KB
testcase_33	AC	53 ms 37,392 KB
testcase_34	AC	52 ms 37,040 KB
testcase_35	AC	52 ms 36,824 KB
testcase_36	AC	53 ms 37,204 KB
testcase_37	AC	53 ms 37,292 KB
testcase_38	AC	53 ms 37,396 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;


//@Japanese
/* PriorityQueueは拡張for文で出すとsortされてない順番で出てくる
 * longのbit演算は1L<<posに注意
 * JOIはMLEが厳しい。最悪shortを使う。
 * ArrayListはオートボクシングが遅いから、最悪自作listを使う
 */

/*略語
 * 2-to, 4-for, 8-from
 * -L -long(型), -P -素数Pを法とした余り
 * a,b -任意の引数, n,m -自然数, p -素数
 * pos -postition
 * abs -絶対値
 * min -minimum, max -maximum, ave -average
 * div -divide
 * pow -power(累乗)
 * ceil -ceiling(天井関数)
 * dt -data
 * ln -length
 * sc -scanner
 * INF -INFINITY
 * e97 -10E9+7=1000000007(prime often used)
 */

// How about n=1, h*w=1*x
// n(E) < 10^6 ? ok : create new Vertex

public class Main {

	public static void main(String[] args) throws Exception {

		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		long[] ps = {2L,3L,5L,7L,11L,13L,17L,19L,23L,29L,31L};//11
		
		int[][] dts = {
				{0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0},
				{1,0,0,0,0,0,0,0,0,0,0},
				{0,1,0,0,0,0,0,0,0,0,0},
				{2,0,0,0,0,0,0,0,0,0,0},
				{0,0,1,0,0,0,0,0,0,0,0},
				{1,1,0,0,0,0,0,0,0,0,0},
				{0,0,0,1,0,0,0,0,0,0,0},
				{3,0,0,0,0,0,0,0,0,0,0},
				{0,2,0,0,0,0,0,0,0,0,0},
				{1,0,1,0,0,0,0,0,0,0,0},
				{0,0,0,0,1,0,0,0,0,0,0},
				{2,1,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,1,0,0,0,0,0},
				{1,0,0,1,0,0,0,0,0,0,0},
				{0,1,1,0,0,0,0,0,0,0,0},
				{4,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,1,0,0,0,0},
				{1,2,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,1,0,0,0},
				{2,0,1,0,0,0,0,0,0,0,0},
				{0,1,0,1,0,0,0,0,0,0,0},
				{1,0,0,0,1,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,1,0,0},
				{3,1,0,0,0,0,0,0,0,0,0},
				{0,0,2,0,0,0,0,0,0,0,0},
				{1,0,0,0,0,1,0,0,0,0,0},
				{0,3,0,0,0,0,0,0,0,0,0},
				{2,0,0,1,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,1,0},
				{1,1,1,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,1},
				{5,0,0,0,0,0,0,0,0,0,0}
		};
		
		int T = sc.nexI();
		
		for(int t=0; t<T; t++) {
			
			long n = sc.nexL();
			//long n = t+1;
			int[] dt = new int[11];
			fill(dt,0);
			
			for(int i=0; i<11; i++) {
				long n2 = n;
				while(n2%ps[i] == 0L) {
					dt[i]++;
					n2 /= ps[i];
				}
			}
			
			int cf = calc(dt, dts[1])*2;
			for(long j=2; j<=31; j++) {
				if(calc(dt, dts[(int) j]) == cf) {
					out.println(n*j);
					break;
				}
			}
		}
		
		
		out.flush();
		return;
	}

	private static int calc(int[] as, int[] bs) {
		int ans = 1;

		for(int i=0; i<as.length; i++) {
			ans *= (as[i]+bs[i]+1);
		}
		return ans;
	}
	
	
	private static int count_devisor(long n) {
		List<Edge> dt = factorizationP(n);
		int ans = 1;
		for(Edge e: dt) {
			ans *= (e.v2+1);
		}
		return ans;
	}
	
	static class Edge { // @Japanese 重み着きのグラフの辺
		int from = -1, v2 = -1;
		long w;

		public Edge(int going2, long weight_route) {
			this.v2 = going2;
			this.w = weight_route;
		}

		public Edge(int come8, int going2, long weight_route) {
			this.from = come8;
			this.v2 = going2;
			this.w = weight_route;
		}

		public void show2() {
			System.out.println(this.from + "->" + this.v2 + " :w=" + this.w);
		}
	}



	private static List<Edge> factorizationP(long n){
							//@Japanese <指数,素数>の形なので注意!!
	    List<Edge> ans = new ArrayList<>();

	    long quotient = n;
	    long devider = 2L;
	    int exponent = 0;

	    while(quotient%devider == 0){
	        quotient /= devider;
	        exponent++;
	    }
	    if(exponent>0) ans.add(new Edge(exponent, devider));

	    devider = 3L;    exponent = 0;
	    while(quotient%devider == 0){
	        quotient /= devider;
	        exponent++;
	    }
	    if(exponent>0) ans.add(new Edge(exponent, devider));

	    devider=1L;
	    while(devider <= Math.sqrt(n)){
	        devider+=4L; exponent=0;
    	    while(quotient%devider == 0){
    	        quotient /= devider;
    	        exponent++;
    	    }
    	    if(exponent>0) ans.add(new Edge(exponent, devider));

	        devider+=2L; exponent=0;
    	    while(quotient%devider == 0){
    	        quotient /= devider;
    	        exponent++;
    	    }
    	    if(exponent>0) ans.add(new Edge(exponent, devider));
	    }
	    if(quotient>1) ans.add(new Edge(1, quotient));
	    return ans;
	}

	static class Net { // @Japanese 重みなしグラフ
		private ArrayList<Node0n> dt = new ArrayList<>();

		Net(int sz) {
			for (int i = 0; i < sz; i++) {
				Node0n node1 = new Node0n();
				dt.add(node1);
			}
		}

		public void add(int v8, int cnct2) {
			dt.get(v8).add(cnct2);
		}

		public void add2(int v1, int v2) {
			dt.get(v1).add(v2);
			dt.get(v2).add(v1);
		}

		public HashSet<Integer> get(int v) {
			return dt.get(v).getAll();
		}

		public int size() {
			return dt.size();
		}

		public int sizeOf(int v) {
			return dt.get(v).size();
		}
		
		public void remove(int v, int e) {
			dt.get(v).remove(e);
		}

		public void clear() {
			for (int i = 0; i < dt.size(); i++)
				dt.get(i).clear();
		}

		public void clear(int v) {
			dt.get(v).clear();
		}

		public static Net make_tree(int tree_size, FastScanner sc) {
			Net tree = new Net(tree_size);
			for (int i = 1; i < tree_size; i++) {
				int s1 = sc.nexI() - 1;
				int g1 = sc.nexI() - 1;
				tree.add2(s1, g1);
			}
			return tree;
		}

		public static Net make_net(int vn, int en, FastScanner sc) {
			Net g = new Net(vn);
			for (int i = 0; i < en; i++) {
				int s1 = sc.nexI() - 1;
				int g1 = sc.nexI() - 1;
				g.add2(s1, g1);
			}
			return g;
		}

		private void add_v(Node0n v_new) {
			dt.add(v_new);
		}

		private int[] get_parent_bfs(int root) {
			int[] ans = new int[this.dt.size()];
			fill(ans, -1);
			ans[root] = INF;

			ArrayDeque<Integer> todo = new ArrayDeque<>();
			todo.add(root);
			while (!todo.isEmpty()) {
				int dw = todo.poll();
				for (int e : this.get(dw)) {
					if (ans[e] < 0) {
						ans[e] = dw;
						todo.add(e);
					}
				}
			}
			return ans;
		}
		private int[] get_dist_bfs(int root) {
			int[] ans = new int[this.dt.size()];
			fill(ans, -1);
			ans[root] = 0;

			ArrayDeque<Integer> todo = new ArrayDeque<>();
			todo.add(root);
			while (!todo.isEmpty()) {
				int dw = todo.poll();
				for (int e : this.get(dw)) {
					if (ans[e] < 0) {
						ans[e] = ans[dw]+1;
						todo.add(e);
					}
				}
			}
			return ans;
		}

		private ArrayList<Integer> get_leaf_list(int exclude) {
			ArrayList<Integer> ans = new ArrayList<>();
			for (int i = 0; i < this.dt.size(); i++) {
				if (i == exclude)
					continue;
				if (this.sizeOf(i) == 1)
					ans.add(i);
			}
			return ans;
		}

		public void show2() {
			for (int i = 0; i < dt.size(); i++) {
				System.out.print(i + ":");
				for (int e : dt.get(i).getAll())
					System.out.print(" " + e);
				System.out.println();
			}
		}
	}

	static class Node0n { // @Japanese 重みなしグラフの頂点
		private HashSet<Integer> next_vs = new HashSet<>();

		public void add(int cnct2) {
			next_vs.add(cnct2);
		}

		public HashSet<Integer> getAll() {
			return next_vs;
		}

		public int size() {
			return next_vs.size();
		}

		public void remove(int e) {
			next_vs.remove(e);
		}
		
		public void clear() {
			next_vs.clear();
		}

		public void addAll(Node0n list2add) {
			this.next_vs.addAll(list2add.next_vs);
		}
	}

	private static final int INF = (int) 3e8;
	private static final long INFL = (long) 1e17;
	private static final int INTMAX = Integer.MAX_VALUE;
	private static final long LONGMAX = Long.MAX_VALUE;
	private static final long e97 = 1000000007L;
	private static final long e99 = 998244353L;
	private static final double PI = Math.PI;

	private static void prYN(boolean ans, PrintWriter out) {
		if(ans) out.println("YES");
		else out.println("NO");
	}
	private static void prYn(boolean ans) {
		if(ans) System.out.println("Yes");
		else System.out.println("No");
	}
	private static void pryesno(boolean ans) {
		if(ans) System.out.println("yes");
		else System.out.println("no");
	}

	private static void assertion(boolean should_true) {
		// throw Error if should_true is not true @Japanese「断言」
		if (!should_true)
			throw new AssertionError();
	}

	private static int abs(int a) {
		return (a >= 0) ? a : -a;
	}

	private static long abs(long a) {
		return (a >= 0L) ? a : -a;
	}

	private static double abs(double a) {
		return (a >= 0.0) ? a : -a;
	}

	private static int getsign(long a) {
		if(a>0) return 1;
		else if(a==0) return 0;
		else return -1;
	}

	private static int min(int a, int b) {
		return (a < b) ? a : b;
	}

	private static long min(long a, long b) {
		return (a < b) ? a : b;
	}

	private static double min(double a, double b) {
		return (a < b) ? a : b;
	}

	private static int max(int a, int b) {
		return (a > b) ? a : b;
	}

	private static long max(long a, long b) {
		return (a > b) ? a : b;
	}

	private static double max(double a, double b) {
		return (a > b) ? a : b;
	}

	private static int pow2(int num2pow) {
		if (num2pow > 4e4)
			throw new IllegalArgumentException("Input is to Large. Use Long.");
		return num2pow * num2pow;
	}

	private static long pow2(long num2pow) {
		if (num2pow > 1e8)
			throw new IllegalArgumentException("Input is to Large. Use PowP.");
		return num2pow * num2pow;
	}

	private static int pow(int num_powered, int index) {
		int ans = 1;
		for (int i = 0; i < index; i++) {
			if (ans >= (INTMAX / num_powered))
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			ans *= num_powered;
		}
		return ans;
	}

	private static long pow(long num_powered, int index) {
		long ans = 1L;
		for (int i = 0; i < index; i++) {
			if (ans >= (LONGMAX / num_powered))
				throw new IllegalArgumentException("Input is to Large. Use PowP.");
			ans *= num_powered;
		}
		return ans;
	}

	private static long powP(long num_powered, long index, long p) {
		// O(log(index))
		// @Japanese 繰り返し二乗法
		if (index == 0L)
			return 1L;
		if (index == 2L) {
			return (pow2(num_powered) % p);
		}

		if (num_powered == 0L)
			return 0L;

		int d = getDigit2(index);
		long[] num_done_by2 = new long[d + 1];
		num_done_by2[0] = num_powered;
		for (int i = 1; i <= d; i++) {
			num_done_by2[i] = num_done_by2[i - 1] * num_done_by2[i - 1];
			num_done_by2[i] %= p;
		}
		long ans = 1L;
		for (int i = d; i >= 0; i--) {
			long cf = (1L << (long) i);
			if (index >= cf) {
				index -= cf;
				ans = ans * num_done_by2[i];
				ans %= p;
			}
		}
		return ans;
	}

	private static double hypod(double a, double b) {
		return Math.sqrt(a * a + b * b);
	}

	private static int getDigit2(long num2know) {
		// O(log(n))
		long compare4 = 1L;
		int digit = 0;
		while (num2know >= compare4) {
			digit++;
			compare4 = (1L << (long) digit);
		}
		return digit;
		// num < 2^digit
	}

	private static int getDigit10(long num2know) {
		// O(log10(n))
		if(num2know<0L) throw new IllegalArgumentException("Input is Negative");
		if(num2know>=1000000000000000000L) return 19;
		long compare4 = 1L;
		int digit = 0;
		while (num2know >= compare4) {
			digit++;
			compare4 *= 10L;
		}
		return digit; // @Japanese num は digit桁の数で、10^digit未満

	}

	private static int divceil(int numerator, int denominator) {
		return (numerator + denominator - 1) / denominator;
	}

	private static long divceil(long numerator, long denominator) {
		return (numerator + denominator - 1L) / denominator;
	}

	private static long factorial(int n) {
		// O(n)
		long ans = 1L;
		for (long i = 2; i <= n; i++) {
			if (ans >= (LONGMAX / i))
				throw new IllegalArgumentException("Input is to Large. Use facP.");
			ans *= i;
		}
		return ans;
	}

	private static long facP(int n, long p) {
		// O(n) see also PermulationCombination:O(max_sz)+Q
		long ans = 1L;
		for (long i = 2; i <= n; i++) {
			ans *= i;
			ans %= p;
		}
		return ans;
	}

	private static long lcm(long m, long n) {
		long ans = m / gcd(m, n);
		if (ans >= (LONGMAX / n))
			throw new IllegalArgumentException("Input is to Large.");
		ans *= n;
		return ans;
	}

	private static long gcd(long m, long n) {
		// O(log(m+n))
		if ((m <= 0L) || (n <= 0L))
			throw new IllegalArgumentException("m and n should be natural.");

		while ((m > 0L) && (n > 0L)) {
			if (m >= n)
				m %= n;
			else
				n %= m;
		}
		if (m > 0L)
			return m;
		else
			return n;
	}

	private static boolean is_prime(long n2check) {
		// @Japanese O(√n)
		if (n2check == 1L)
			return false;
		for (long i = 2L; i <= Math.sqrt(n2check); i++) {
			if (n2check % i == 0L)
				return false;
		}
		return true;
	}
	private static int isSquare(long n) {
		double sq = Math.sqrt(n);
		long ans = (long)sq;
		if((ans *ans) == n) return (int)ans;
		else return -1;
	}



	private static int safe_mod(int n, int p) {
		n %= p;
		if (n >= 0)
			return n;
		return (n + p);
	}

	private static long safe_mod(long n, long p) {
		n %= p;
		if (n >= 0L)
			return n;
		return (n + p);
	}

	private static long modinv(long n, long p) {
		// @Japanese 逆元を求める
		// O(10log(n))
		// pは素数でなくてもよい
		// ネットから拾ってきたのが理解不能だったので、行列計算を用いて非効率的アルゴリズムを書いた

		n %= p;
		if ((p == 1L) || (gcd(n, p) != 1L))
			throw new IllegalArgumentException("n and p should be coprime.");

		// @Japanese
		// yn≡1(mod p)
		// <-> xp+yn=1; (n<p)
		// ...(sx+ty)a+(ux+vy)b=1 (|sv-tu|=1)
		// ...(sx+ty)a+(ux+vy)=1
		// <- sx+ty=0, ux+vy=1

		long a = p, b = n, s = 1L, t = 0L, u = 0L, v = 1L;
		while (b > 1) {
			long quo = a / b, rem = a % b;
			a = b;
			b = rem;
			long s2 = s * quo + u, t2 = t * quo + v;
			u = s;
			v = t;
			s = s2;
			t = t2;
		}
		long det = s * v - t * u;
		if (abs(det) != 1L)
			throw new ArithmeticException("My algorithm was Wrong!!");
		s /= det;
		s %= p;
		if (s < 0L)
			s += p;
		return s;
	}

	private static int minAll(int[] dt4min) {
		// O(n)
		int min = INF;
		for (int element : dt4min) {
			if (element < min)
				min = element;
		}
		return min;
	}

	private static long minAll(long[] dt4min) {
		// O(n)
		long min = INFL;
		for (long element : dt4min) {
			if (element < min)
				min = element;
		}
		return min;
	}

	private static int maxAll(int[] dt4max) {
		// O(n)
		int max = -INF;
		for (int element : dt4max) {
			if (element > max)
				max = element;
		}
		return max;
	}

	private static long maxAll(long[] dt4max) {
		// O(n)
		long max = -INFL;
		for (long element : dt4max) {
			if (element > max)
				max = element;
		}
		return max;
	}

	private static int sumAll(int[] dt4sum) {
		// O(n)
		int sum_of_dt = 0;
		for (int element : dt4sum) {
			if (sum_of_dt > (INTMAX - element))
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			sum_of_dt += element;
		}
		return sum_of_dt;
	}

	private static long sumAll(long[] dt4sum) {
		// O(n)
		long sum_of_dt = 0L;
		for (long element : dt4sum) {
			if (sum_of_dt > (LONGMAX - element))
				throw new IllegalArgumentException("Input is to Large.");
			sum_of_dt += element;
		}
		return sum_of_dt;
	}

	private static int sumAll(ArrayList<Integer> dt4sum) {
		int sum_of_dt = 0;
		for (long element : dt4sum) {
			if (sum_of_dt > (INTMAX - element))
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			sum_of_dt += element;
		}
		return sum_of_dt;
	}

	private static int[] reverse(int[] as) {
		int ln = as.length;
		int[] bs = new int[ln];
		for (int i = 0; i < ln; i++)
			bs[i] = as[ln - i - 1];
		return bs;
	}
	private static long[] reverse(long[] as) {
		int ln = as.length;
		long[] bs = new long[ln];
		for (int i = 0; i < ln; i++)
			bs[i] = as[ln - i - 1];
		return bs;
	}
	private static char[] reverse(char[] as) {
		int ln = as.length;
		char[] bs = new char[ln];
		for (int i = 0; i < ln; i++)
			bs[i] = as[ln - i - 1];
		return bs;
	}

	private static void reverseSub(int[] as, int S_include, int Gnot_include) {
		// O(G-S)
		int ln = Gnot_include - S_include;

		int[] bs = new int[ln];
		for (int i = S_include; i < Gnot_include; i++)
			bs[i - S_include] = as[i];
		for (int i = 0; i < ln; i++)
			as[i + S_include] = bs[ln - i - 1];
	}

	private static boolean is_in_area(int y, int x, int height, int width) {
		if (y < 0)
			return false;
		if (x < 0)
			return false;
		if (y >= height)
			return false;
		if (x >= width)
			return false;
		return true;
	}

	private static boolean is_in_area(Vector v, int height, int width) {
		if (v.y < 0)
			return false;
		if (v.x < 0)
			return false;
		if (v.y >= height)
			return false;
		if (v.x >= width)
			return false;
		return true;
	}

	private static int nC2(int n) {
		return ((n * (n - 1)) / 2);
	}

	private static long nC2(long n) {
		return ((n * (n - 1L)) / 2L);
	}

	private static long nCk_unsafe(int n, int k) {
		long ans = factorial(n);
		ans /= factorial(k);
		ans /= factorial(n-k);
		return ans;
	}
	private static int iflag(int pos) {
		if (pos >= 32)
			throw new IllegalArgumentException("Input is to Large. Use Long.");
		return (1 << pos);
	}

	private static long flag(int pos) {
		if (pos >= 64)
			throw new IllegalArgumentException("Input is to Large. Use Long.");
		return (1L << (long) pos);
	}

	private static boolean isFlaged(int bit, int pos) {
		if (pos >= 32)
			throw new IllegalArgumentException("Input is to Large.");
		return ((bit & (1 << pos)) != 0);
	}

	private static boolean isFlaged(long bit, int pos) {
		if (pos >= 64)
			throw new IllegalArgumentException("Input is to Large.");
		return ((bit & (1L << (long) pos)) != 0L);
	}

	private static int deflag(int bit, int pos) {
		return (bit & (~(1 << pos)));
	}

	private static int countFlaged(int bit) {
		int ans = 0;
		for (int i = 0; i < 31; i++) {
			if ((bit & (1 << i)) != 0)
				ans++;
		}
		return ans;
	}

	private static int countFlaged(long bit) {
		int ans = 0;
		for (long i = 0L; i < 63L; i++) {
			if ((bit & (1L << i)) != 0L)
				ans++;
		}
		return ans;
	}

	private static int[] Xdir4 = { 1, 0, 0, -1 };
	private static int[] Ydir4 = { 0, 1, -1, 0 };
	private static int[] Xdir8 = { 1, 1, 1, 0, 0, -1, -1, -1 };
	private static int[] Ydir8 = { 1, 0, -1, 1, -1, 1, 0, -1 };

	public static int biSearch(long[] dt, long target) {
		// O(log(dt.length))
		// dt should be sorted in 0->INF
		// return adress of target
		int left = 0, right = dt.length - 1;
		int mid = -1;
		while (left <= right) {
			mid = ((right + left) / 2);
			if (dt[mid] == target)
				return mid;
			if (dt[mid] < target)
				left = (mid + 1);
			else
				right = (mid - 1);
		}
		return -1;
	}

	public static int biSearchMax(long[] dt, long target) {
		// O(log(dt.length))
		// dt should be sorted in 0->INF
		int left = -1, right = dt.length, mid = -1;
		while ((right - left) > 1) {
			mid = ((right + left) / 2);
			if (dt[mid] <= target)
				left = mid;
			else
				right = mid;
		}
		return left;
		// @Japanese target以下の最大のaddress
	}

	public static int biSearchMin(long[] dt, long target) {
		// O(log(dt.length))
		// dt should be sorted in 0->INF
		int left = -1, right = dt.length, mid = -1;
		while ((right - left) > 1) {
			mid = ((right + left) / 2);
			if (dt[mid] <= target)
				left = mid;
			else
				right = mid;
		}
		return right;
		// @Japanese targetより大きい最小のaddress
	}

	private static void fill(boolean[] target, boolean reset) {
		for (int i = 0; i < target.length; i++)
			target[i] = reset;
	}

	private static void fill(int[] target, int reset) {
		for (int i = 0; i < target.length; i++)
			target[i] = reset;
	}

	private static void fill(long[] target, long reset) {
		for (int i = 0; i < target.length; i++)
			target[i] = reset;
	}

	private static void fill(char[] target, char reset) {
		for (int i = 0; i < target.length; i++)
			target[i] = reset;
	}

	private static void fill(double[] target, double reset) {
		for (int i = 0; i < target.length; i++)
			target[i] = reset;
	}

	private static void fill(boolean[][] target, boolean reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				target[i][j] = reset;
			}
		}
	}

	private static void fill(int[][] target, int reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				target[i][j] = reset;
			}
		}
	}

	private static void fill(long[][] target, long reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				target[i][j] = reset;
			}
		}
	}

	private static void fill(char[][] target, char reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				target[i][j] = reset;
			}
		}
	}

	private static void fill(double[][] target, double reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				target[i][j] = reset;
			}
		}
	}

	private static void fill(int[][][] target, int reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				for (int k = 0; k < target[i][j].length; k++) {
					target[i][j][k] = reset;
				}
			}
		}
	}

	private static void fill(long[][][] target, long reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				for (int k = 0; k < target[i][j].length; k++) {
					target[i][j][k] = reset;
				}
			}
		}
	}
	private static void fill(double[][][] target, double reset) {
		for (int i = 0; i < target.length; i++) {
			for (int j = 0; j < target[i].length; j++) {
				for (int k = 0; k < target[i][j].length; k++) {
					target[i][j][k] = reset;
				}
			}
		}
	}

	private static void fill_parent(int[] parent) {
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
	}

	private static void showBit(int bit) {
		for (int i = 0; i < getDigit2(bit); i++) {
			if (isFlaged(bit, i))
				System.out.print("O");
			else
				System.out.print(".");
		}
		System.out.println();
	}

	private static void showBit(long bit) {
		for (int i = 0; i < getDigit2(bit); i++) {
			if (isFlaged(bit, i))
				System.out.print("O");
			else
				System.out.print(".");
		}
		System.out.println();
	}

	static void show2(boolean[][] dt, String cmnt) {
		for (int i = 0; i < dt.length; i++) {
			for (int j = 0; j < dt[i].length; j++) {
				if (dt[i][j])
					System.out.print("O");
				else
					System.out.print(".");
			}
			if (!cmnt.equals(""))
				System.out.print("<-" + cmnt);
			System.out.println(" :" + i);
		}
	}

	static void show2(int[][] dt, String cmnt) {
		for (int i = 0; i < dt.length; i++) {
			for (int j = 0; j < dt[i].length; j++)
				System.out.print(dt[i][j] + ",");
			if (!cmnt.equals(""))
				System.out.print("<-" + cmnt);
			System.out.println(" :" + i);
		}
	}

	static void show2(long[][] dt, String cmnt) {
		for (int i = 0; i < dt.length; i++) {
			for (int j = 0; j < dt[i].length; j++)
				System.out.print(dt[i][j] + ",");
			if (!cmnt.equals(""))
				System.out.print("<-" + cmnt);
			System.out.println(" :" + i);
		}
	}

	static void show2(ArrayDeque<Long> dt) {
		long element = 0;
		while (dt.size() > 0) {
			element = dt.removeFirst();
			System.out.print(element);
		}
		System.out.println("\n");
	}

	static void show2(List<Object> dt) {
		for (int i = 0; i < dt.size(); i++)
			System.out.print(dt.get(i) + ",");
		System.out.println("\n");
	}

	private static void prtlnas(int[] array, PrintWriter out) {
		for (int e: array)
			out.println(e);
		out.flush();
	}

	private static void prtlnas(long[] array, PrintWriter out) {
		for (long e: array)
			out.println(e);
		out.flush();
	}

	private static void prtlnas(ArrayList<Object> array, PrintWriter out) {
		for (Object e: array)
			out.println(e);
		out.flush();
	}

	private static void prtspas(int[] array, PrintWriter out) {
		out.print(array[0]);
		for (int i = 1; i < array.length; i++)
			out.print(" " + array[i]);
		out.println();
		//out.flush();
	}

	private static void prtspas(long[] array, PrintWriter out) {
		out.print(array[0]);
		for (int i = 1; i < array.length; i++)
			out.print(" " + array[i]);
		out.println();
		out.flush();
	}

	private static void prtspas(double[] array, PrintWriter out) {
		out.print(array[0]);
		for (int i = 1; i < array.length; i++)
			out.print(" " + array[i]);
		out.println();
		out.flush();
	}

	private static void prtspas(List<Integer> array, PrintWriter out) {
		if (array.isEmpty())
			return;
		out.print(array.get(0));
		for (int i = 1; i < array.size(); i++)
			out.print(" " + array.get(i));
		out.println();
		out.flush();
	}

	static class Vector {
		int x, y;
		public Vector(int sx, int sy) {
			this.x = sx;
			this.y = sy;
		}
		public boolean equals(Vector v) {
			return (this.x == v.x && this.y == v.y);
		}
		public void show2() {
			System.out.println(this.x + ", " + this.y);
		}
		public static int dist2(Vector a, Vector b) {
			int dx = abs(a.x - b.x);
			int dy = abs(a.y - b.y);
			if (dx > 3e4)
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			if (dy > 3e4)
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			return (dx * dx + dy * dy);
		}
	}
	static class LVector {
		long x, y;
		public LVector(long sx, long sy) {
			this.x = sx;
			this.y = sy;
		}
		public boolean equals(LVector v) {
			return (this.x == v.x && this.y == v.y);
		}
		public void show2() {
			System.out.println(this.x + ", " + this.y);
		}
		public static long dist2(Vector a, Vector b) {
			int dx = abs(a.x - b.x);
			int dy = abs(a.y - b.y);
			if (dx > 1e8)
				throw new IllegalArgumentException("Input is to Large.");
			if (dy > 1e8)
				throw new IllegalArgumentException("Input is to Large.");
			return (dx * dx + dy * dy);
		}
	}

	static class CompVector implements Comparator<Vector> {
		public int compare(Vector a, Vector b) {
			if (a.x == b.x)
				return a.y - b.y;
			else
				return a.x - b.x;
		}
	}
	static class CompLVector implements Comparator<LVector> {
		public int compare(LVector a, LVector b) {
			if (a.x == b.x)
				return getsign(a.y - b.y);
			else
				return getsign(a.x - b.x);
		}
	}

	static class FastScanner {
		//@Japanese ネットから拾ってきた。よく分からんし、著作権侵害
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private static boolean isPrintableChar(int c) {
			return (33 <= c) && (c <= 126);
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nexL() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b) || b == ':') {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nexI() {
			long nl = nexL();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
				throw new NumberFormatException();
			}
			return (int) nl;
		}

		public double nexD() {
			return Double.parseDouble(next());
		}

		public int[] ai(int ln) {
			int[] as = new int[ln];
			for (int i = 0; i < ln; i++) {
				as[i]=nexI();
			}
			return as;
		}

		public long[] al(int ln) {
			long[] as = new long[ln];
			for (int i = 0; i < ln; i++) {
				as[i]=nexL();
			}
			return as;
		}
		// a means array
		public void ai(int[]... array) {
			for (int i = 0; i < array[0].length; i++) {
				for (int j = 0; j < array.length; j++) {
					array[j][i] = nexI();
				}
			}
			return;
		}

		public void al(long[]... array) {
			for (int i = 0; i < array[0].length; i++) {
				for (int j = 0; j < array.length; j++) {
					array[j][i] = nexL();
				}
			}
			return;
		}

		public void aimin1(int[] array) {
			for (int i = 0; i < array.length; i++) {
				array[i] = nexI() - 1;
			}
			return;
		}

		public void aD(double[]... array) {
			for (int i = 0; i < array[0].length; i++) {
				for (int j = 0; j < array.length; j++) {
					array[j][i] = nexD();
				}
			}
			return;
		}

		public void ai2d(int[][] array) {
			for (int i = 0; i < array.length; i++) {
				for (int j = 0; j < array[0].length; j++) {
					array[i][j] = nexI();
				}
			}
			return;
		}

		public void al2d(long[][] array) {
			for (int i = 0; i < array.length; i++) {
				for (int j = 0; j < array[0].length; j++) {
					array[i][j] = nexL();
				}
			}
			return;
		}
	}
}
// END OF THE CODE
yukicoder

結果

テストケース

ソースコード
