Submission #1176647


Source Code Expand

import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

		Pair[] x = new Pair[n];
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();

			x[i] = new Pair(tmp, i + 1);
		}
		Arrays.sort(x);

		int[] d = new int[n * n];
		int l = 0;
		for (int i = 0; i < n; i++) {
			if (d[x[i].a - 1] != 0) {
				pr.println("No");
				return;
			}
			d[x[i].a - 1] = x[i].b;

			int cnt = x[i].b - 1;
			while (cnt > 0 && l < x[i].a) {
				if (d[l] != 0) {
					l++;
				} else {
					d[l++] = x[i].b;
					cnt--;
				}
			}
			if (cnt > 0) {
				pr.println("No");
				return;
			}
		}

		int r = n * n - 1;
		for (int i = n - 1; i >= 0; i--) {
			if (d[x[i].a - 1] != x[i].b) {
				pr.println("xxx");
				return;
			}

			int cnt = n - x[i].b;
			while (cnt > 0 && r >= x[i].a) {
				if (d[r] != 0) {
					r--;
				} else {
					d[r--] = x[i].b;
					cnt--;
				}
			}
			if (cnt > 0) {
				pr.println("No");
				return;
			}
		}

		for (int i = 0; i < n; i++) {
			if (d[i] == 0) {
				pr.println("No");
				return;
			}
		}

		pr.println("Yes");
		for (int i = 0; i < n * n; i++) {
			if (i > 0) {
				pr.print(' ');
			}
			pr.print(d[i]);
		}
		pr.println();
	}

	private static class Pair implements Comparable<Pair> {
		int a;
		int b;

		Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}

		@Override
		public int compareTo(Pair o) {
			if (a == o.a) {
				Integer.compare(b, o.b);
			}

			return Integer.compare(a, o.a);
		}

		@Override
		public int hashCode() {
			return Integer.hashCode(a);
		}

		@Override
		public String toString() {
			// [xxx, xxxx]
			StringBuilder stmp = new StringBuilder(32);
			stmp.append('[');
			stmp.append(a);
			stmp.append(',');
			stmp.append(' ');
			stmp.append(b);
			stmp.append(']');

			return stmp.toString();
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		private boolean isPrintable(int ch) {
			return ch >= '!' && ch <= '~';
		}

		private boolean isCRLF(int ch) {
			return ch == '\n' || ch == '\r' || ch == -1;
		}

		private int nextPrintable() {
			try {
				int ch;
				while (!isPrintable(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}

				return ch;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		String next() {
			try {
				int ch = nextPrintable();
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (isPrintable(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		int nextInt() {
			try {
				// parseInt from Integer.parseInt()
				boolean negative = false;
				int res = 0;
				int limit = -Integer.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Integer.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				int multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		long nextLong() {
			try {
				// parseLong from Long.parseLong()
				boolean negative = false;
				long res = 0;
				long limit = -Long.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Long.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				long multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		float nextFloat() {
			return Float.parseFloat(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			try {
				int ch;
				while (isCRLF(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (!isCRLF(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new NoSuchElementException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}

Submission Info

Submission Time
Task D - K-th K
User garnacha
Language Java8 (OpenJDK 1.8.0)
Score 800
Code Size 5890 Byte
Status AC
Exec Time 234 ms
Memory 36588 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 2
AC × 49
Set Name Test Cases
Sample 0_00.txt, 0_01.txt
All 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt
Case Name Status Exec Time Memory
0_00.txt AC 70 ms 21588 KB
0_01.txt AC 70 ms 21460 KB
1_00.txt AC 71 ms 20564 KB
1_01.txt AC 179 ms 34216 KB
1_02.txt AC 171 ms 32996 KB
1_03.txt AC 166 ms 36352 KB
1_04.txt AC 169 ms 29308 KB
1_05.txt AC 171 ms 34704 KB
1_06.txt AC 159 ms 36380 KB
1_07.txt AC 180 ms 36020 KB
1_08.txt AC 170 ms 32792 KB
1_09.txt AC 83 ms 18644 KB
1_10.txt AC 78 ms 19028 KB
1_11.txt AC 83 ms 21460 KB
1_12.txt AC 83 ms 20308 KB
1_13.txt AC 79 ms 20692 KB
1_14.txt AC 75 ms 17364 KB
1_15.txt AC 160 ms 31300 KB
1_16.txt AC 74 ms 19540 KB
1_17.txt AC 78 ms 22100 KB
1_18.txt AC 167 ms 27628 KB
1_19.txt AC 178 ms 35632 KB
1_20.txt AC 164 ms 30244 KB
1_21.txt AC 167 ms 32232 KB
1_22.txt AC 162 ms 31204 KB
1_23.txt AC 91 ms 19796 KB
1_24.txt AC 179 ms 36588 KB
1_25.txt AC 159 ms 28984 KB
1_26.txt AC 80 ms 22100 KB
1_27.txt AC 87 ms 19924 KB
1_28.txt AC 74 ms 21332 KB
1_29.txt AC 84 ms 20820 KB
1_30.txt AC 169 ms 32100 KB
1_31.txt AC 234 ms 34624 KB
1_32.txt AC 73 ms 21460 KB
1_33.txt AC 166 ms 30824 KB
1_34.txt AC 76 ms 21328 KB
1_35.txt AC 87 ms 19924 KB
1_36.txt AC 168 ms 32428 KB
1_37.txt AC 173 ms 32616 KB
1_38.txt AC 162 ms 31148 KB
1_39.txt AC 202 ms 19796 KB
1_40.txt AC 130 ms 25300 KB
1_41.txt AC 80 ms 19284 KB
1_42.txt AC 148 ms 28620 KB
1_43.txt AC 170 ms 31884 KB
1_44.txt AC 75 ms 21460 KB
1_45.txt AC 74 ms 18900 KB
1_46.txt AC 76 ms 21460 KB