結果
問題 | No.689 E869120 and Constructing Array 3 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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;}@Overridepublic Iterator<Integer> iterator() {return new PrimeIterator();}private class PrimeIterator implements Iterator<Integer> {int index;PrimeIterator() {index = -1;}@Overridepublic boolean hasNext() {if (index == -1) {return n >= 2;} else {return 2 * (index + 1) + 1 <= n;}}@Overridepublic 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);}}}