Submission #1232728
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.Comparator; import java.util.InputMismatchException; import java.util.stream.Collectors; import java.util.stream.IntStream; import java.util.stream.LongStream; import java.util.stream.Stream; public class Main { static void solve(FastScanner sc, PrintWriter out) { int N = sc.ni(); int[] p = IntStream.of(sc.nia(N)).map(d -> d - 1).toArray(); long[] a = LongStream.range(1, N + 1).toArray(); long[] b = reverse(a); long sum = a[p[0]] + b[p[0]] + 1; for (int i = 1; i < N; i++, sum++) { long diff = sum - (a[p[i]] + b[p[i]]); if (diff == 0) continue; b[p[i]] += diff; if (diff < 0) { for (int j = p[i] + 1; j < N; j++) { a[j] -= diff; b[j] += diff; } } else { for (int j = p[i] - 1; j >= 0; j--) { a[j] -= diff; b[j] += diff; } } } long minA = LongStream.of(a).min().getAsLong(); if (minA < 1) { long offset = 1 - minA; a = Arrays.stream(a).map(i -> i + offset).toArray(); } long minB = LongStream.of(b).min().getAsLong(); if (minB < 1) { long offset = 1 - minB; b = Arrays.stream(b).map(i -> i + offset).toArray(); } out.println(join(" ", a)); out.println(join(" ", b)); } static long[] reverse(long[] array) { int len = array.length; long[] ret = new long[len]; for (int i = 0; i < len; i++) { ret[i] = array[len - 1 - i]; } return ret; } static String join(String delimiter, long[] array) { return Arrays.stream(array).mapToObj(String::valueOf).collect(Collectors.joining(delimiter)); } public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); PrintWriter out = new PrintWriter(System.out); solve(sc, out); out.flush(); } static class FastScanner { private final InputStream is; private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; FastScanner(InputStream is) { this.is = is; } char nc() { return (char) skip(); } char[] nca(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } char[][] nca2(int n, int m) { char[][] buf = new char[m][n]; for (int i = 0; i < m; i++) { buf[i] = nca(n); } return buf; } String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while (!(isSpaceChar(b))) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } int ni() { int num = 0, b; boolean minus = false; while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ; if (b == '-') { minus = true; b = readByte(); } while (true) { if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } b = readByte(); } } int[] nia(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } long nl() { long num = 0, b; boolean minus = false; while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ; if (b == '-') { minus = true; b = readByte(); } while (true) { if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } b = readByte(); } } double nd() { return Double.parseDouble(ns()); } private int readByte() { if (lenbuf == -1) throw new InputMismatchException(); if (ptrbuf >= lenbuf) { ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return -1; } return inbuf[ptrbuf++]; } private int skip() { int b; while ((b = readByte()) != -1 && isSpaceChar(b)) ; return b; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } } }
Submission Info
Submission Time | |
---|---|
Task | B - Construct Sequences |
User | keitoff314 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 5465 Byte |
Status | AC |
Exec Time | 391 ms |
Memory | 33236 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt, example2.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, example0.txt, example1.txt, example2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 242 ms | 27756 KB |
001.txt | AC | 198 ms | 24916 KB |
002.txt | AC | 192 ms | 28356 KB |
003.txt | AC | 182 ms | 22996 KB |
004.txt | AC | 185 ms | 24276 KB |
005.txt | AC | 346 ms | 33104 KB |
006.txt | AC | 204 ms | 22868 KB |
007.txt | AC | 330 ms | 30828 KB |
008.txt | AC | 253 ms | 27220 KB |
009.txt | AC | 348 ms | 33108 KB |
010.txt | AC | 356 ms | 33236 KB |
011.txt | AC | 363 ms | 32468 KB |
012.txt | AC | 362 ms | 31700 KB |
013.txt | AC | 391 ms | 33024 KB |
014.txt | AC | 379 ms | 33128 KB |
015.txt | AC | 384 ms | 29324 KB |
016.txt | AC | 354 ms | 30872 KB |
017.txt | AC | 349 ms | 31316 KB |
018.txt | AC | 386 ms | 33132 KB |
example0.txt | AC | 165 ms | 26056 KB |
example1.txt | AC | 168 ms | 24404 KB |
example2.txt | AC | 163 ms | 26064 KB |