結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
ユーザー CaliPotaCaliPota
提出日時 2021-03-12 22:57:58
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 17,890 bytes
コンパイル時間 2,685 ms
コンパイル使用メモリ 91,912 KB
実行使用メモリ 56,868 KB
最終ジャッジ日時 2024-10-14 13:32:30
合計ジャッジ時間 13,426 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
36,584 KB
testcase_01 AC 47 ms
36,948 KB
testcase_02 AC 45 ms
36,584 KB
testcase_03 AC 50 ms
36,972 KB
testcase_04 AC 47 ms
36,608 KB
testcase_05 AC 50 ms
37,032 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 47 ms
36,672 KB
testcase_10 AC 48 ms
36,808 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 47 ms
36,888 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 46 ms
36,808 KB
testcase_19 AC 45 ms
37,020 KB
testcase_20 WA -
testcase_21 AC 45 ms
36,992 KB
testcase_22 AC 267 ms
52,276 KB
testcase_23 AC 161 ms
42,252 KB
testcase_24 AC 159 ms
41,856 KB
testcase_25 AC 278 ms
54,840 KB
testcase_26 AC 326 ms
56,428 KB
testcase_27 AC 293 ms
51,656 KB
testcase_28 AC 379 ms
56,868 KB
testcase_29 AC 214 ms
46,824 KB
testcase_30 AC 169 ms
42,456 KB
testcase_31 AC 343 ms
55,656 KB
testcase_32 AC 215 ms
47,480 KB
testcase_33 AC 89 ms
39,944 KB
testcase_34 AC 225 ms
47,028 KB
testcase_35 AC 389 ms
56,444 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 AC 49 ms
36,892 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.TreeSet;

public class Main {

	//PriorityQueueは拡張for文で出すとsortされてない順番で出てくる
	//longのbit演算は1L<<posに注意
	//long long
	//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(よく使われる素数)

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);


		int n = sc.nexI();
		int[] as = new int[n];
		sc.ai(as);
		
		TreeSet<Integer> dta = new TreeSet<>();
		for(int i=0; i<n; i++) dta.add(as[i]);
		
		
		
		int ans = 0;
		if(as[n-1] != dta.last()) ans++;
		for(int i=1; i<n; i++) {
			if(as[i] == dta.first()) continue;
			if(as[i-1] == as[i]) continue;
			if(as[i-1] >= dta.floor(as[i]-1)) continue;
			ans++;
		}
		System.out.println(ans);
		out.flush();
		return;
	}
	
	private static void mumbojumbo() {
		int[] is = Xdir4;is=Ydir4;is=Xdir8;is=Ydir8;
		abs(0);abs(0.0);min(0,0);min(0L,0L);min(0.0,0.0);
		max(0,0);max(0L,0L);max(0.0,0.0);pow2(0);pow2(0L);
		pow(0,0);pow(0L,0);powP(0L,0L,e97);hypod(0.0,0.0);
		getDigit10(0L);divceil(0,0);divceil(0L,0L);
		factorial(0);facP(0,e97);lcm(0L,0L);gcd(0L,0L);
		is_prime(0L);modinv(0L,0L);
		minAll(is);minAll(new long[0]);
		maxAll(is);maxAll(new long[0]);
		sumAll(is);sumAll(new long[0]);
		sumAll(new ArrayList<>());reverse(new int[0]);
		is_in_area(0,0,0,0);is_in_area(new Vector(0,0),0,0);
		nC2(0);nC2(0L);iflag(0);flag(0);deflag(0, 0);
		countFlaged(0);countFlaged(0L);
		fill(new boolean[0],false);fill(is,0);
		fill(new long[0],0L);fill(new char[0],'\0');
		fill(new double[0],0.0);fill(new boolean[0][0],false);
		fill(new int[0][0],0);fill(new long[0][0],0L);
		fill(new char[0][0],'\0');fill(new double[0][0],0.0);
		fill(new int[0][0][0],0);fill(new long[0][0][0],0L);
		showBit(0);showBit(0L);
		prtlnas(new ArrayList<>());prtlnas(is);prtlnas(new long[0]);
		prtspas(new ArrayList<>());prtspas(is);prtspas(new long[0]);
		
	}

	private static int INF = (int) 1e8;
	private static long INFL = (long) 1e17;
	private static long e97 = 1000000007L;

	

	private static void assertion(boolean should_true) {
		//should_trueがtrueでなければエラーを起こす。「断言」
		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>=0) ? a: -a;
	}
	private static double abs(double a) {
		return (a>=0.0) ? a: -a;
	}
	
	private static int min(int a, int b) {
		return (a>b) ? b : a;
	}
	private static long min(long a, long b) {
		return (a>b) ? b : a;
	}
	private static double min(double a, double b) {
		return (a>b) ? b : a;
	}

	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) {
		return num2pow*num2pow;
	}
	private static long pow2(long num2pow) {
		return num2pow*num2pow;
	}


	private static int pow(int num_powered, int index) {
		int ans = 1;
		for(int i=0; i<index; i++) {
			ans *= num_powered;
			assertion(ans>=0);
		}
		return ans;
	}
	private static long pow(long num_powered, int index) {
		long ans = 1L;
		for(int i=0; i<index; i++) {
			ans *= num_powered;
			assertion(ans>=0L);
		}
		return ans;
	}
	private static long powP(long num_powered, long index, long p) {
		//繰り返し二乗法
		if(num_powered==0L) return 0L;
		if(index==0L) return 1L;
		if(index==2L) {
			long ans = num_powered*num_powered;
			assertion(ans>0);
			return ans%p;
		}

		int d = getDigit2(index);

		long next = 0L;
		long[] num_done_by2 = new long[d+1];
		num_done_by2[0] = num_powered;
		for(int i=1; i<=d; i++) {
			next = num_done_by2[i-1]*num_done_by2[i-1];
			assertion(next>0);
			num_done_by2[i] = next%p;
		}
		long ans=1L;
		for(int i=d; i>=0; i--) {
			if(index >= (1L<<(long)i)) {
				index -= (1L<<(long)i);
				ans = ans*num_done_by2[i];
				assertion(ans>0);
				ans *= p;
			}
 		}
		return ans%p;
	}
	private static double hypod(double a, double b) {
		return Math.sqrt(a*a+b*b);
	}

	private static int getDigit2(long num2know) {
		long compare4 = 1L;
		int digit = 0;
		while(num2know > compare4) {
			digit ++;
			compare4 = (1L<<(long)digit);
		}
		return digit; //numは2^d以下
	}
	private static int getDigit10(long num2know) {
		long compare4 = 1L;
		int digit = 0;
		while(num2know >= compare4) {
			digit ++;
			compare4 *= 10L;
		}
		return digit; //numはd桁の数で、10^dより小さい

	}


	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) {
		long ans=1L;
		for(long i=n; i>0; i--) {
			ans *= i;
			assertion(ans>=0L);
		}
		return ans;
	}
	private static long facP(int n, long p) {
		long ans=1L;
		for(long i=n; i>0; i--) {
			ans *= i;
			ans %= p;
		}
		return ans;
	}

	private static long lcm(long m, long n) {
		assertion((m>0L) && (n>0L));
		long ans = m/gcd(m,n);
		ans *= n;
		return ans;
	}
	private static long gcd(long m, long n) {
		//if(isINFL(-m)) return n;
		assertion((m>=0L) && (n>=0L));
		if(m < n) return gcd(n, m);
		if(n == 0) return m;
		return gcd(n, m % n);
	}

	private static boolean is_prime(long n2check) {
		if(n2check==1L) return false;
		for(long i=2L; i<=Math.sqrt(n2check); i++) {
			if(n2check%i == 0) return false;
		}
		return true;
	}

	private static long modinv(long n, long p) {
		assertion((n>0L)&&(p>1L)&&(gcd(n,p)==1L));
		//a⊥p, >1に注意
		n %= p;

		//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=1, t=0, u=0, v=1;
		while(b>1) {
			long quo = a/b;
			long 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;
		assertion(abs(det)==1);
		s /= det;

		/*long b = p, u = 1L, v = 0L;//動作原理不明
		while (b > 0) {
			long t = a / b;
			long pe = a%b;
			a = b;
			b = pe;
			pe = u-t*v;
			u = v;
			v = pe;
		}*/
		s %= p;
		if(s < 0L) s += p;
		return s;
	}

	private static int minAll(int[] dt4min) {
		int min = INF;
		for(int i=0; i<dt4min.length; i++) {
			if(dt4min[i] < min) min = dt4min[i];
		}
		return min;
	}
	private static long minAll(long[] dt4min) {
		long min = INFL;
		for(int i=0; i<dt4min.length; i++) {
			if(dt4min[i] < min) min = dt4min[i];
		}
		return min;
	}
	private static int maxAll(int[] dt4max) {
		int max = -INF;
		for(int i=0; i<dt4max.length; i++) {
			if(dt4max[i] < max) max = dt4max[i];
		}
		return max;
	}
	private static long maxAll(long[] dt4max) {
		long max = -INFL;
		for(int i=0; i<dt4max.length; i++) {
			if(dt4max[i] < max) max = dt4max[i];
		}
		return max;
	}

	private static int sumAll(int[] dt4sum) {
		int sum_of_dt = 0;
		for(int element: dt4sum) {
			sum_of_dt += element;
		}
		return sum_of_dt;
	}
	private static long sumAll(long[] dt4sum) {
		long sum_of_dt = 0L;
		for(long element: dt4sum) {
			sum_of_dt += element;
		}
		return sum_of_dt;
	}
	private static long sumAll(ArrayList<Long> dt4sum) {
		long sum_of_dt = 0L;
		for(long element: dt4sum) {
			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 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 int iflag(int pos) {
		assertion(pos<31);
		return (1<<pos);
	}
	private static long flag(int pos) {
		assertion(pos<63);
		return (1L<<(long)pos);
	}
	private static boolean isFlaged(int bit, int pos) {
		if((bit&(1<<pos)) > 0) return true;
		else return false;
	}
	private static boolean isFlaged(long bit, int pos) {
		if((bit&(1L<<(long)pos)) > 0L) return true;
		else return false;
	}
	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=0; i<63L; i++) {
			if((bit&(1L<<i)) > 0) 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(int[] dt, int 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) {
		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;	//target未満の最大のaddress
	}
	public static int biSearchMin(long[] dt, long target) {
		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;	//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 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 = new PrintWriter(System.out);
		for(int i=0; i<array.length; i++) {
			out.println(array[i]);
		}
		out.flush();
	}
	private static void prtlnas(long[] array) {
		PrintWriter out = new PrintWriter(System.out);
		for(int i=0; i<array.length; i++) {
			out.println(array[i]);
		}
		out.flush();
	}
	private static void prtlnas(ArrayList<Object> array) {
		PrintWriter out = new PrintWriter(System.out);
		for(int i=0; i<array.size(); i++) {
			out.println(array.get(i));
		}
		out.flush();
	}
	private static void prtspas(int[] array) {
		PrintWriter out = new PrintWriter(System.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 = new PrintWriter(System.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(ArrayList<Object> array) {
		PrintWriter out = new PrintWriter(System.out);
		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;
		}
	}
	
	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 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());}
		//aは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.length; i++) {
		 		array[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;
		}
	}

}
//END OF THE CODE
0