CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Taulukot
Sender:
Submission time:2015-10-09 23:23:43 +0300
Language:Java
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED26
#2ACCEPTED29
#3ACCEPTED45
Test results
testverdicttimegroup
#1ACCEPTED0.17 s1details
#2ACCEPTED0.18 s1details
#3ACCEPTED0.17 s1details
#4ACCEPTED0.17 s1details
#5ACCEPTED0.20 s1details
#6ACCEPTED0.17 s2details
#7ACCEPTED0.19 s2details
#8ACCEPTED0.17 s2details
#9ACCEPTED0.18 s2details
#10ACCEPTED0.17 s2details
#11ACCEPTED0.46 s3details
#12ACCEPTED0.40 s3details
#13ACCEPTED0.42 s3details
#14ACCEPTED0.41 s3details
#15ACCEPTED0.43 s3details

Code

//package alkuluvut;

import java.util.Arrays;
import java.util.TreeSet;

/**
 *
 * @author Adreno
 */
public class Alkuluvut {

    public static boolean[] eiOleAlkuLuku;
            
    public static void main(String[] args) {
        IO io = new IO();
        int n = io.nextInt();
        //int n = 100000;
        int max = 2*n+2;
        eiOleAlkuLuku = new boolean[max];
        for (int i = 2; i < max; i++) {
            if (eiOleAlkuLuku[i]) continue;
            for (int j = i*i; j < max && j > 0; j += i) {
                eiOleAlkuLuku[j] = true;
            }
        }
        TreeSet<Integer> alkuluvut = new TreeSet<>();
        for (int i=2; i<max; i++) {
            if (eiOleAlkuLuku[i]) continue;
            alkuluvut.add(i);
        }

        boolean[] kaytetty = new boolean[n+1];
        int pointer = 0;
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i=n; i>=1; i--) {
            if (kaytetty[i]) continue;
            int nextPossible = i+i+1;
            while (true) {
                nextPossible = alkuluvut.lower(nextPossible);
                int counterPart = nextPossible - i;
                if (kaytetty[counterPart]) continue;
                kaytetty[counterPart] = true;
                kaytetty[i] = true;
                a[pointer] = counterPart;
                b[pointer] = i;
                pointer++;
                if (i != counterPart) {
                    a[pointer] = i;
                    b[pointer] = counterPart;
                }
                pointer++;
                break;
            }
        }
        
        for (int i=0; i<n; i++) io.print(a[i] + " ");
        io.println();
        for (int i=0; i<n; i++) io.print(b[i] + " ");
        io.println();
        
        io.close();
    }

}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1

correct output


user output


Test 2

Group: 1

Verdict: ACCEPTED

input
4

correct output
1 2 3 4 
2 1 4 3 

user output
3 4 1 2 
4 3 2 1 

Test 3

Group: 1

Verdict: ACCEPTED

input
5

correct output
1 2 3 4 5 
1 5 4 3 2 

user output
2 5 3 4 1 
5 2 4 3 1 

Test 4

Group: 1

Verdict: ACCEPTED

input
8

correct output
1 2 3 4 5 6 7 8 
2 1 4 3 8 7 6 5 

user output
5 8 6 7 3 4 1 2 
8 5 7 6 4 3 2 1 

Test 5

Group: 1

Verdict: ACCEPTED

input
9

correct output
1 2 3 4 5 6 7 8 9 
1 5 4 3 2 7 6 9 8 

user output
8 9 6 7 2 5 3 4 1 
9 8 7 6 5 2 4 3 1 

Test 6

Group: 2

Verdict: ACCEPTED

input
77

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
74 77 75 76 66 73 67 72 68 71 ...

Test 7

Group: 2

Verdict: ACCEPTED

input
70

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
69 70 63 68 64 67 65 66 51 62 ...

Test 8

Group: 2

Verdict: ACCEPTED

input
72

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
67 72 68 71 69 70 65 66 63 64 ...

Test 9

Group: 2

Verdict: ACCEPTED

input
86

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
81 86 82 85 83 84 77 80 78 79 ...

Test 10

Group: 2

Verdict: ACCEPTED

input
68

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
63 68 64 67 65 66 51 62 52 61 ...

Test 11

Group: 3

Verdict: ACCEPTED

input
90764

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
90759 90764 90760 90763 90761 ...

Test 12

Group: 3

Verdict: ACCEPTED

input
97976

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
97955 97976 97956 97975 97957 ...

Test 13

Group: 3

Verdict: ACCEPTED

input
96762

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
96751 96762 96752 96761 96753 ...

Test 14

Group: 3

Verdict: ACCEPTED

input
94823

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
94820 94823 94821 94822 94800 ...

Test 15

Group: 3

Verdict: ACCEPTED

input
91479

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
91478 91479 91476 91477 91458 ...