結果

問題 No.689 E869120 and Constructing Array 3
ユーザー Grenache
提出日時 2018-05-18 23:40:09
言語 Java
(openjdk 23)
結果
AC  
実行時間 201 ms / 1,000 ms
コード長 4,417 bytes
コンパイル時間 4,341 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 46,752 KB
最終ジャッジ日時 2024-06-28 14:03:44
合計ジャッジ時間 8,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
public class Main_yukicoder689 {
    private static Scanner sc;
    private static Printer pr;
    private static void solve() {
        Prime prime = new Prime(1_000_000);
        List<Integer> p2 = new ArrayList<>();
        List<Integer> p4 = new ArrayList<>();
        List<Integer> p6 = new ArrayList<>();
        for (int p : prime) {
            if (p <= 10) {
                continue;
            }
            if (!prime.isPrime(p + 2) && !prime.isPrime(p + 4)) {
                p2.add(p);
            } else if (!prime.isPrime(p - 2) && !prime.isPrime(p + 2)) {
                p4.add(p);
            } else if (!prime.isPrime(p - 4) && !prime.isPrime(p - 2)) {
                p6.add(p);
            }
        }
//      pr.println(p2.size());
//      pr.println(p4.size());
//      pr.println(p6.size());
        int k = sc.nextInt();
        if (k == 0) {
            pr.println(1);
            pr.println(1);
            return;
        }
        List<Integer> ans = new ArrayList<>();
        {
            int tmp = (int)Math.sqrt(k);
            for (int i = 0; i < tmp; i++) {
                ans.add(2);
            }
            for (int i = 0; i < tmp; i++) {
                ans.add(p2.get(i) - 2);
            }
            k -= tmp * tmp;
        }
        {
            int tmp = (int)Math.sqrt(k);
            for (int i = 0; i < tmp; i++) {
                ans.add(4);
            }
            for (int i = 0; i < tmp; i++) {
                ans.add(p4.get(i) - 4);
            }
            k -= tmp * tmp;
        }
        {
            for (int i = 0; i < k; i++) {
                if (i == 0) {
                    ans.add(6);
                }
                ans.add(p6.get(i) - 6);
            }
        }
        pr.println(ans.size());
        for (int i = 0, size = ans.size(); i < size; i++) {
            if (i > 0) {
                pr.print(' ');
            }
            pr.print(ans.get(i));
        }
        pr.println();
        /*
        int cnt = 0;
        for (int i = 0, size = ans.size(); i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (prime.isPrime(ans.get(i) + ans.get(j))) {
                    cnt++;
//                  pr.printf("%d %d %d %d\n", i, j, ans.get(i), ans.get(j));
                }
            }
        }
        pr.println(ans.size());
        if (cnt != k) {
            pr.println(cnt);
        }
//      */
    }
    static class Prime implements Iterable<Integer> {
        private int n;
        private BitSet p;
        Prime(int n) {
            this.n = n;
            p = new BitSet(n / 2);
            int m = (int)Math.sqrt(n);
//          for (int i = 1; i <= m; i++) {
            for (int bi = p.nextClearBit(0); 2 * (bi + 1) + 1 <= m; bi = p.nextClearBit(bi + 1)) {
                long i = bi + 1;
//              if (p.get(i - 1)) {
//                  continue;
//              }
                for (long j = 2 * i * (i + 1); 2 * j + 1 <= n; j += 2 * i + 1) {
                    p.set((int)(j - 1));
                }
            }
        }
        boolean isPrime(int n) {
            if (n == 2) {
                return true;
            }
            if (n == 1 || (n & 0x1) == 0) {
                return false;
            }
            return !p.get(n / 2 - 1);
        }
        List<Integer> getPrimeList() {
            List<Integer> ret = new ArrayList<>();
            for (int p : this) {
                ret.add(p);
            }
            return ret;
        }
        Map<Long, Integer> primeFactorize(long x) {
            Map<Long, Integer> hm = new TreeMap<>();
            long n = x;
            for (int p : this) {
                if ((long)p * p > n) {
                    break;
                }
                int cnt = 0;
                while (n % p == 0) {
                    cnt++;
                    n /= p;
                }
                if (cnt > 0) {
                    hm.put((long)p, cnt);
                }
            }
            if (n != 1) {
                hm.put(n, 1);
            }
            return hm;
        }
        @Override
        public Iterator<Integer> iterator() {
            return new PrimeIterator();
        }
        private class PrimeIterator implements Iterator<Integer> {
            int index;
            PrimeIterator() {
                index = -1;
            }
            @Override
            public boolean hasNext() {
                if (index == -1) {
                    return n >= 2;
                } else {
                    return 2 * (index + 1) + 1 <= n;
                }
            }
            @Override
            public Integer next() {
                if (index == -1) {
                    if (n >= 2) {
                        index = p.nextClearBit(0);
                        return 2;
                    } else {
                        throw new NoSuchElementException();
                    }
                } else {
                    int ret = 2 * (index + 1) + 1;
                    if (ret <= n) {
                        index = p.nextClearBit(index + 1);
                        return ret;
                    } else {
                        throw new NoSuchElementException();
                    }
                }
            }
        }
        static boolean isPrime(long n) {
            if (n == 2) {
                return true;
            }
            if (n == 1 || (n & 0x1) == 0) {
                return false;
            }
            for (long i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }
    // ---------------------------------------------------
    public static void main(String[] args) {
        sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
        pr = new Printer(System.out);
        solve();
//      pr.close();
        pr.flush();
//      sc.close();
    }
    static String INPUT = null;
    private static class Printer extends PrintWriter {
        Printer(OutputStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0