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
AC × 3
AC × 22
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