結果

問題 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