結果
| 問題 | No.1256 連続整数列 |
| ユーザー |
 Ken Fuchiwaki
|
| 提出日時 | 2020-10-18 15:20:17 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 66 ms / 2,000 ms |
| コード長 | 35,464 bytes |
| コンパイル時間 | 4,161 ms |
| コンパイル使用メモリ | 94,952 KB |
| 実行使用メモリ | 49,612 KB |
| 最終ジャッジ日時 | 2024-07-21 05:23:17 |
| 合計ジャッジ時間 | 7,368 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 64 ms
48,868 KB |
| testcase_01 | AC | 63 ms
49,148 KB |
| testcase_02 | AC | 65 ms
48,876 KB |
| testcase_03 | AC | 64 ms
49,192 KB |
| testcase_04 | AC | 63 ms
49,076 KB |
| testcase_05 | AC | 64 ms
49,428 KB |
| testcase_06 | AC | 64 ms
49,360 KB |
| testcase_07 | AC | 65 ms
49,600 KB |
| testcase_08 | AC | 64 ms
49,200 KB |
| testcase_09 | AC | 63 ms
49,512 KB |
| testcase_10 | AC | 63 ms
49,448 KB |
| testcase_11 | AC | 66 ms
48,884 KB |
| testcase_12 | AC | 65 ms
49,348 KB |
| testcase_13 | AC | 65 ms
49,336 KB |
| testcase_14 | AC | 62 ms
49,332 KB |
| testcase_15 | AC | 63 ms
49,448 KB |
| testcase_16 | AC | 65 ms
49,480 KB |
| testcase_17 | AC | 66 ms
49,320 KB |
| testcase_18 | AC | 65 ms
48,804 KB |
| testcase_19 | AC | 64 ms
49,288 KB |
| testcase_20 | AC | 66 ms
49,400 KB |
| testcase_21 | AC | 64 ms
49,612 KB |
| testcase_22 | AC | 64 ms
49,500 KB |
| testcase_23 | AC | 63 ms
49,556 KB |
| testcase_24 | AC | 64 ms
48,872 KB |
| testcase_25 | AC | 62 ms
49,156 KB |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
public class Main {
public static void main(String[] args) {
long a = sc.nextLong()*2;
if(a==2){
System.out.println("NO");
return;
}
boolean yes = false;
for (long i=1;i*i<=a;i++){
if (a%i==0){
long lef = i+1-2*a/i;
if (lef%2==0){
long v = lef/2;
long u = i-v;
if (v+1<u){
yes=true;
break;
}
}
}
}
if (yes)System.out.println("YES");
else System.out.println("NO");
}
public static final long MOD = 1000000007L;
public static final int tenE9 = 1000000000;
public static final int INF = Integer.MAX_VALUE/2;
public static final int dataDigit = 10000;
static Basic basic = new Basic();
static FastScanner sc = new FastScanner();
public static class FastScanner {
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 nextLong() {
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)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() { return Double.parseDouble(next());}
}
public static class Basic {
//math
private final int MAX = 51*dataDigit;
private final long MOD = Main.MOD;
private final long[] fac = new long[MAX];
private final long[] finv = new long[MAX];
private final long[] inv = new long[MAX];
public long factorial(long num) {
if (num < 2) return 1;
else return num * factorial(num - 1);
}//階乗
public long modFactorial(long num) {
if (num < 2) return 1;
else return num*modFactorial(num-1)%MOD;
}//余り階乗
public double log(double base, double antilogarithm) {
return Math.log(antilogarithm) / Math.log(base);
}//対数
public long gcd(long x, long y) {
if (y == 0) return x;
else return gcd(y, x % y);
}//最大公約数
public long lcm(long x, long y) {
return x / gcd(x, y) * y;
}//最小公倍数
public HashMap<Long, Long> factorization(long num) {
HashMap<Long, Long> hash = new HashMap<>();
long n = num;
long count = 2;
while (n > 1) {
while (n % count == 0) {
n /= count;
if (hash.containsKey(count)) hash.put(count, hash.get(count) + 1);
else hash.put(count, 1L);
}
count++;
}
return hash;
}//素因数分解
public int sum(int[] num) {
int ans = 0;
for (int j : num) {
ans += j;
}
return ans;
}//総和
public int[] reduce(int small, int big) {
int ins = 2;
while (ins <= small) {
if (small % ins == 0 && big % ins == 0) {
small /= ins;
big /= ins;
ins = 2;
} else {
ins++;
}
}
return new int[]{small, big};
}//約分
public int reduceCount(int small, int big) {
int ins = 2;
int ans = 0;
while (ins <= small) {
if (small % ins == 0 && big % ins == 0) {
small /= ins;
big /= ins;
ins = 2;
ans++;
} else {
ins++;
}
}
return ans;
}//約分回数
public long modPow(long a, long n, long mod) {
long res = 1;
while (n > 0) {
if ((n & 1) != 0) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
public long pow(long a, long n) {
long res = 1;
while (n > 0) {
if ((n & 1) != 0) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
public long modInv(long a, long mod) {
return modPow(a, mod - 2, mod);
}//単位元は素数であることが必須。
public void dataInit() {
fac[0] = 1;
fac[1] = 1;
finv[0] = 1;
finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[(int)(MOD % i)] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
public long combination(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n-k]%MOD)% MOD;
}
public long permutation(int n, int k){
return fac[n]*finv[n-k]%MOD;
}
public long hCOM(int n, int k) {
return combination(n + k - 1, k);
}
public boolean[] getIsPrimeArray(int max){
boolean[] ret = new boolean[max+1];
Arrays.fill(ret,true);
ret[0]=false;
ret[1]=false;
for (int i=2;i<=max;i++){
if (ret[i]){
int c = 2*i;
while (c<=max){
ret[c]=false;
c+=i;
}
}
}
return ret;
}
public int digits(long n) {
return String.valueOf(n).length();
}
public boolean isPrime(int N) {
if(N <= 1)
return false;
else if(N == 2)
return true;
for(int i = 2; i <= Math.sqrt(N); i++)
if(N % i == 0)
return false;
return true;
}
public long modInvert(long a, long m){
long b = m;
long u = 1;
long v = 0;
while (b!=0){
long t = a/b;
a-=t*b;
long c = a;
a=b;
b=c;
u-=t*v;
c=u;
u=v;
v=c;
}
u%=m;
if (u<0)u+=m;
return u;
}//単位元が素数でなくても可能。a,mは互いに素であることが必須。得られる逆元は最小値。より高速。
public long ceil_pow2(long n){
long x = 0;
while (1L<<x<n)x++;
return x;
}
public static class ChineseRemainder{
long p;
long q;
public long mod(long a, long m){
return (a%m+m)%m;
}
public long extGCD(long a, long b){
if (b==0){ p=1;q=0;return a; }
long s = p;
p=q;
q=s;
long d = extGCD(b,a%b);
q-=a/b*p;
return d;
}
public long ChineseRem(long b1,long m1,long b2,long m2){
p=0;
q=0;
long d = extGCD(m1, m2); // p is inv of m1/d (mod. m2/d)
if ((b2 - b1) % d != 0) return -1;//none
long m = m1 * (m2/d); // lcm of (m1, m2)
long tmp = (b2 - b1) / d * p % (m2/d);
return mod(b1 + m1 * tmp, m);//mod m
}
}
//array
public int[] remove(int[] ar, int pos) {
int[] ret = new int[ar.length - 1];
for (int i = 0; i < pos; i++) ret[i] = ar[i];
for (int i = pos + 1; i < ar.length; i++) ret[i - 1] = ar[i];
return ret;
}
public int[] nextIntArray(int size,int cons){
int[] ret = new int[size];
for (int i=0;i<size;i++)ret[i]=sc.nextInt()+cons;
return ret;
}
public long[] nextLongArray(int size,int cons){
long[] ret = new long[size];
for (int i=0;i<size;i++)ret[i]=sc.nextLong()+cons;
return ret;
}
public int[] reverse(int[] ar){
int[] ret = new int[ar.length];
for (int i=0;i<ar.length;i++){
ret[i]=ar[ar.length-1-i];
}
return ret;
}
public long[] cumulative(long[] ar,BiFunction<Long,Long,Long> op,long def){
long[] ret = new long[ar.length+1];
ret[0]=def;
for (int i=0;i<ar.length;i++){
ret[i+1]=op.apply(ret[i],ar[i]);
}
return ret;
}
public int median(int[] a) {
Arrays.sort(a);
if(a.length % 2 == 1)
return a[a.length/2];
else
return (a[a.length/2-1] + a[a.length/2]) / 2;
}
public int binarySearch(int[] array, int target) {
int pos = -1;
int left = 0;
int right = array.length - 1;
int middle;
while (pos == -1 && left <= right) {
middle = (left + right) / 2;
if (array[middle] == target) pos = middle;
else if (array[middle] > target) right = middle - 1;
else left = middle + 1;
}
return pos;
}
public int lowerBound(int[] a, int key) {
if(a[a.length-1] < key)
return a.length;
int lb = 0, ub = a.length-1, mid;
do {
mid = (ub+lb)/2;
if(a[mid] < key)
lb = mid + 1;
else
ub = mid;
}while(lb < ub);
return ub;
}
public int upperBound(int[] a, int key) {
if(a[a.length-1] <= key)
return a.length;
int lb = 0, ub = a.length-1, mid;
do {
mid = (ub+lb)/2;
if(a[mid] <= key)
lb = mid + 1;
else
ub = mid;
}while(lb < ub);
return ub;
}
public int count(int[] a, int key) {
return upperBound(a, key) - lowerBound(a, key);
}
public List<String> Permutation = new ArrayList<>();
public void initPermutation(){Permutation.clear();}
public void permutationList(String q, String ans){
if(q.length() <= 1) {
Permutation.add(ans + q);
}
else {
for (int i = 0; i < q.length(); i++) {
permutationList(q.substring(0, i) + q.substring(i + 1), ans + q.charAt(i));
}
}
}
public String next_permutation(String s){
ArrayList<Character> list = new ArrayList<>();
for (int i=0; i<s.length(); i++) list.add(s.charAt(i));
int pivotPos = -1;
char pivot = 0;
for (int i=list.size()-2; i>=0; i--) {
if (list.get(i) < list.get(i+1)) {
pivotPos = i;
pivot = list.get(i);
break;
}
}
if (pivotPos==-1 && pivot==0) return "Final";
int L = pivotPos+1, R = list.size()-1;
int minPos = -1;
char min = Character.MAX_VALUE;
for (int i=R; i>=L; i--) {
if (pivot < list.get(i)) {
if (list.get(i) < min) {
min = list.get(i);
minPos = i;
}
}
}
Collections.swap(list, pivotPos, minPos);
Collections.sort(list.subList(L, R+1));
StringBuilder sb = new StringBuilder();
for (int i=0; i<list.size(); i++) sb.append(list.get(i));
return sb.toString();
}
public Comparator<String> dictionarySort = new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int ret = 0;
int p = 0;
int min = Math.min(o1.length(),o2.length());
boolean b = true;
while (b&&p<min){
if (o1.charAt(p)<o2.charAt(p)){
ret=-1;
b=false;
}else if (o1.charAt(p)>o2.charAt(p)){
ret=1;
b=false;
}
p++;
}
if (ret==0){
if (o1.length()<o2.length())ret=-1;
else if (o1.length()>o2.length())ret=1;
}
return ret;
}
};
public int[] forEach(int[] array, ArrayReplace ar){
int[] ret = new int[array.length];
for (int i=0;i<array.length;i++)ret[i]=ar.replace(i);
return ret;
}
//graph
public void warshall_floyd(int[][] d) {
int n = d.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}//隣接行列が引数。辺が無い場合、INFを入力。
public int[] bellman_ford(int[][] d, int size, int start){
int e = d.length;
int[] ans = new int[size];
Arrays.fill(ans,Integer.MAX_VALUE);
ans[start]=0;
for (int i=0;i<size;i++){
for (int[] a : d) {
if (ans[a[1]] > ans[a[0]] + a[2]) {
ans[a[1]] = ans[a[0]] + a[2];
if (i == size - 1) {
System.out.println("negative loop");
break;
}
}
}
}
return ans;
}//辺を配列の要素として管理。
public interface ArrayReplace{
int replace(int num);
}
}
public static class Queue<T>{
private final int max = 10000000;
private final T[] queue = (T[]) new Object[max];
private int tail = 0; private int head = 0;
public void init(){this.head = 0; tail = 0;}
public boolean isEmpty(){return (head==tail);}
public boolean isFull(){return (head == (tail+1)%max);}
public void enqueue(T v){
if (isFull()){
System.out.println("error: queue is full.");
return;
}
queue[tail++] = v;
if (tail == max) tail = 0;
}
public T dequeue(){
if (isEmpty()){
System.out.println("error: queue is empty");
return null;
}
T res = queue[head];
++head;
if (head == max) head = 0;
return res;
}
}
public static class Deque<T>{
private final int max = 10000000;
private final T[] queue = (T[]) new Object[max];
private int tail = 0; private int head = 0;
public void init(){this.head = 0; tail = 0;}
public boolean isEmpty(){return (head==tail);}
public boolean isFull(){
return (head == (tail+1)%max);
}
public void pushFirst(T v){
if (isFull()){
System.out.println("error: queue is full.");
return;
}
head--;
if (head==-1)head=max-1;
queue[head] = v;
}
public void pushLast(T v){
if (isFull()){
System.out.println("error: queue is full.");
return;
}
queue[tail++] = v;
if (tail == max) tail = 0;
}
public T popFirst(){
if (isEmpty()){
System.out.println("error: queue is empty");
return null;
}
T res = queue[head];
++head;
if (head == max) head = 0;
return res;
}
public T popLast(){
if (isEmpty()){
System.out.println("error: queue is empty");
return null;
}
if (--tail==-1)tail=max-1;
return queue[tail];
}
public T peekFirst(){
if (isEmpty()){
System.out.println("error: queue is empty");
return null;
}
return queue[head];
}
public T peekLast(){
if (isEmpty()){
System.out.println("error: queue is empty");
return null;
}
return queue[tail];
}
}
public static class Stack<T>{
private final int max = 1000000;
private final T[] stack =(T[]) new Object[max];
private int top = 0;
public boolean isEmpty(){return (top==0);}
public boolean isFull(){return (top==max);}
public void init(){top=0;}
public void push(T v){
if (isFull()){
System.out.println("error: stack is full.");
return;
}
stack[top++] = v;
}
public T pop(){
if (isEmpty()){
System.out.println("error: stack is empty");
return null;
}
return stack[--top];
}
public T peek(){
if (isEmpty()){
System.out.println("error: stack is empty");
return null;
}
return stack[top];
}
}
public static class Pair<K,V>{
private K A;
private V B;
Pair(K a,V b){
A=a;
B=b;
}
public void changeA(K a){A=a;}
public void changeB(V b){B=b;}
public void changeAB(K a,V b){A=a;B=b;}
public static Comparator numberSortWithA = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
Pair p = (Pair)o1;
Pair q = (Pair)o2;
if ((int)p.A<(int)q.A)return -1;
else if ((int)p.A==(int)q.A){
if ((int)p.B<(int)q.B)return -1;
else if ((int)p.B==(int)q.B)return 0;
else return 1;
}
else return 1;
}
};
public static Comparator numberSortWithB = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
Pair p = (Pair)o1;
Pair q = (Pair)o2;
if ((int)p.B<(int)q.B)return -1;
else if ((int)p.B==(int)q.B){
if ((int)p.A<(int)q.A)return -1;
else if ((int)p.A==(int)q.A)return 0;
else return 1;
}
else return 1;
}
};
}
public static class Graph{
final HashMap<Integer,HashSet<Integer>> graph = new HashMap<>();
final int Size;
Graph(int size){
for (int i=0;i<size;i++)graph.put(i,new HashSet<>());
Size = size;
}
public void addEdge(int node1,int node2){
if (graph.containsKey(node1)&&graph.containsKey(node2)){
graph.get(node1).add(node2);
graph.get(node2).add(node1);
}
}
public void addDirectEdge(int from,int to){
if (graph.containsKey(from)&&graph.containsKey(to)){
graph.get(from).add(to);
}
}
public int[] depth(int root){
Queue<Integer> q = new Queue<>();
q.enqueue(root);
boolean[] seen = new boolean[Size];
Arrays.fill(seen, false);
seen[root]=true;
int[] depth = new int[Size];
Arrays.fill(depth,-1);
depth[root]=0;
while (!q.isEmpty()){
int v = q.dequeue();
for (int u : graph.get(v)){
if (!seen[u]){
seen[u]=true;
q.enqueue(u);
depth[u]=depth[v]+1;
}
}
}
return depth;
}
public HashSet<Integer> getConnected(int pos){return graph.get(pos);}
public boolean isConnected(int from,int to){return graph.get(from).contains(to);}
public int diameter(){
int[] f = depth(0);
int m = Arrays.stream(f).max().getAsInt();
int n = basic.binarySearch(f,m);
int[] s = depth(n);
return Arrays.stream(s).max().getAsInt();
}
}
public static class Tree extends Graph{
ArrayList<ArrayList<Integer>> parent;
ArrayList<Integer> dist;
Tree(int size) {
super(size);
parent = new ArrayList<>();
dist = new ArrayList<>();
}
void initLCA(int root){
int V = super.Size;
int K = 1;
while ((1<<K)<V)K++;
for (int i=0;i<K;i++){
ArrayList<Integer> a = new ArrayList<>();
for (int j=0;j<V;j++)a.add(-1);
parent.add(a);
}
for (int i=0;i<V;i++)dist.add(-1);
dfs(root,-1,0);
for (int k=0;k+1<K;k++){
for (int v=0;v<V;v++){
if (parent.get(k).get(v)<0){
parent.get(k+1).set(v,-1);
}else {
parent.get(k+1).set(v,parent.get(k).get(parent.get(k).get(v)));
}
}
}
}
void dfs(int v, int p, int d){
parent.get(0).set(v,p);
dist.set(v,d);
for (int e :super.graph.get(v)){
if (e!=p)dfs(e,v,d+1);
}
}
int queryLCA(int U, int V){
int u = U;
int v = V;
if (dist.get(u)<dist.get(v)){
int y = u;u=v;v=y;
}
int K = parent.size();
for (int k=0;k<K;k++){
if ((((dist.get(u)-dist.get(v))>>k)&1)!=0)u=parent.get(k).get(u);
}
if (u==v)return u;
for (int k=K-1;k>=0;k--){
if (!Objects.equals(parent.get(k).get(u), parent.get(k).get(v))){
u=parent.get(k).get(u);
v=parent.get(k).get(v);
}
}
return parent.get(0).get(u);
}
HashSet<Integer> leaf(){
HashSet<Integer> ret = new HashSet<>();
int[] p = new int[super.Size];
for (int i=0;i<p.length;i++){
p[parent.get(0).get(i)]++;
}
for (int i=0;i<p.length;i++)if (p[i]==0)leaf().add(i);
return ret;
}
}
public static class WeightedGraph{
private final HashMap<Integer,HashMap<Integer,Integer>> graph = new HashMap<>();
private final int Size;
private long[] Depth;
WeightedGraph(int size){
for (int i=0;i<size;i++)graph.put(i,new HashMap<>());
Size = size;
}
public void addEdge(int node1,int node2,int weight){
if (graph.containsKey(node1)&&graph.containsKey(node2)){
graph.get(node1).put(node2,weight);
graph.get(node2).put(node1,weight);
}
}
public void addDirectEdge(int from,int to,int weight){
if (graph.containsKey(from)&&graph.containsKey(to)){
graph.get(from).put(to,weight);
}
}
public int[] dijkstra(int root){
Comparator<int[]> c = new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1], o2[1]);
}
};
PriorityQueue<int[]> q = new PriorityQueue<>(c);
q.add(new int[]{root,0});
int[] ret = new int[Size];
Arrays.fill(ret,Integer.MAX_VALUE);
ret[root]=0;
while (!q.isEmpty()){
int[] v = q.poll();
if (v[1]<=ret[v[0]]){
HashMap<Integer,Integer> h = graph.get(v[0]);
for (int u : h.keySet()){
if (ret[u]>v[1]+h.get(u)){
ret[u]=v[1]+h.get(u);
q.add(new int[]{u,ret[u]});
}
}
}
}
return ret;
}
public long[] Depth(int root){
Queue<Integer> q = new Queue<>();
q.enqueue(root);
boolean[] seen = new boolean[Size];
Arrays.fill(seen, false);
seen[root]=true;
long[] depth = new long[Size];
depth[root]=0;
while (!q.isEmpty()){
int v = q.dequeue();
for (int u : graph.get(v).keySet()){
if (!seen[u]){
seen[u]=true;
q.enqueue(u);
depth[u]=depth[v]+graph.get(v).get(u);
}
}
}
Depth = depth.clone();
return depth;
}
}
public static class UnionFindTree{
int[] parent;
int[] rank;
int[] Size;
int Number;
public UnionFindTree(int size){
this.parent = new int[size];
this.rank = new int[size];
this.Size = new int[size];
makeSet();
}
public void makeSet(){
for (int i=0;i<Size.length;i++){
parent[i]=i;
rank[i]=0;
Size[i]=1;
}
Number= Size.length;
}
public void unite(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
if (rank[xRoot]>rank[yRoot]){
parent[yRoot] = xRoot;
Size[xRoot]+=Size[yRoot];
Number--;
}else if (rank[xRoot]<rank[yRoot]){
parent[xRoot] = yRoot;
Size[yRoot]+=Size[xRoot];
Number--;
}else if (xRoot!=yRoot){
parent[yRoot] = xRoot;
rank[xRoot]++;
Size[xRoot]+=Size[yRoot];
Number--;
}
}
public int find(int i){
if (i!= parent[i]){
parent[i]=find(parent[i]);
}
return parent[i];
}
public boolean same(int x, int y){
return find(x) == find(y);
}
public int getSize(int i){return Size[find(i)];}
boolean isConnected(){
return Number<2;
}
ArrayList<Integer> roots(){
ArrayList<Integer> set = new ArrayList<>();
for (int i=0;i<parent.length;i++){
if (i==parent[i])set.add(i);
}
return set;
}
}
public static class BitSearch<T>{
T[] Array;
int Width;
int Length;
BitSearch(T[] t, int width){
Array = t;
Width = width;
Length = Array.length;
}
void start(){
long max = (long)Math.pow(Width,Length);
for (long i=0;i<max;i++){
StringBuilder s = new StringBuilder(Long.toString(i, Width));
while (s.length()<Length) s.insert(0, "0");
run(s);
}
}
void run(StringBuilder s){
}
}
public static class SegTree{
private int n = 0;
private final long[] d;
private final BiFunction<Long,Long,Long> op;
private final long e;
private final int Size;
private final long Log;
SegTree(int N,BiFunction<Long,Long,Long> OP,long E){
n=N;
op=OP;
e=E;
long log = basic.ceil_pow2(N);
Log=log;
int size = 1<<log;
d =new long[2*size];
Arrays.fill(d, e);
Size=size;
}
SegTree(int N, long[] S, BiFunction<Long,Long,Long> OP,long E){
n=N;
op=OP;
e=E;
long log = basic.ceil_pow2(N);
int size = 1<<log;
d =new long[2*size];
Log=log;
Arrays.fill(d, e);
if (n >= 0) System.arraycopy(S, 0, d, size, n);
for (int i=size-1;i>=1;i--){
update(i);
}
Size=size;
}
void set(int p,long x){
p += Size;
d[p] = x;
for (int i = 1; i <= Log; i++) update(p >> i);
}
long get(int p){return d[p+Size];}
long prod(int l,int r){
long sml = e,smr=e;
l+=Size;
r+=Size;
while (l<r){
if ((l&1)!=0)sml=op.apply(sml,d[l++]);
if ((r&1)!=0)smr=op.apply(d[--r],smr);
l>>=1;
r>>=1;
}
return op.apply(sml,smr);
}
long all_prod(){return d[1];}
int max_right(int l, Function<Long,Boolean> f){
if (l==n)return n;
l+= Size;
long sm = e;
do {
while (l%2==0)l>>=1;
if (!f.apply(op.apply(sm,d[l]))){
while (l<Size){
l*=2;
if (f.apply(op.apply(sm,d[l]))){
sm= op.apply(sm,d[l]);
l++;
}
}
return l-Size;
}
sm= op.apply(sm,d[l]);
l++;
}while ((l&-l)!=l);
return n;
}
int min_left(int r,Function<Long,Boolean> f){
if (r==0)return 0;
r+=Size;
long sm=e;
do {
r--;
while (r>1&&(r%2)!=0)r>>=1;
if (!f.apply(op.apply(d[r],sm))){
while (r<Size){
r=r*2+1;
if (f.apply(op.apply(d[r],sm))){
sm= op.apply(d[r],sm);
r--;
}
}
return r+1-Size;
}
sm= op.apply(d[r],sm);
}while ((r&-r)!=r);
return 0;
}
private void update(int k){
d[k]=op.apply(d[2*k],d[2*k+1]);
}
}
public static class TrieTree{
int char_size;
int base;
final ArrayList<Node> nodes = new ArrayList<>();
final ArrayList<String> Words = new ArrayList<>();
final HashMap<String,Integer> WordMap = new HashMap<>();
TrieTree(int charSize,int Base){
char_size=charSize;
base=Base;
nodes.add(new Node(0));
}
class Node{
int content;
int[] children = new int[char_size];
int commonNodes;
HashSet<String> acceptedWords = new HashSet<>();
Node(int Content){
content=Content;
Arrays.fill(children,-1);
commonNodes=0;
}
}
void insert(String word,int word_id){
Words.add(word);
WordMap.put(word,word_id);
char[] w = word.toCharArray();
int current_node = 0;
for (int i=0;i<w.length;i++){
int content = w[i]-base;
int[] Children = nodes.get(current_node).children;
if (Children[content]==-1){
nodes.add(new Node(content));
Children[content]=nodes.size()-1;
}
int next_node = Children[content];
nodes.get(current_node).commonNodes++;
current_node=next_node;
}
nodes.get(current_node).commonNodes++;
nodes.get(current_node).acceptedWords.add(word);
}
void insert(String word){
insert(word,Words.size());
}
boolean search(String word){
char[] w = word.toCharArray();
int current_node = 0;
for (int i=0;i<w.length;i++){
int content = w[i]-base;
int[] Children = nodes.get(current_node).children;
if (Children[content]==-1){
return false;
}
current_node= Children[content];
}
return nodes.get(current_node).acceptedWords.contains(word);
}
}
}