CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Tekijät
Sender:Grez
Submission time:2020-11-07 14:30:56 +0200
Language:C++ (C++17)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#30.03 s2, 3details
#4--3details
#5--3details
#6ACCEPTED0.04 s3details
#7ACCEPTED0.04 s3details

Code

#include <iostream>
#include <unordered_map>
using namespace std;

int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
    139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
    307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
    479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
    863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };

int main()
{
    int amo;
    cin >> amo;
    
    int num;
    int prime, b;
    long sum = 0;

    unordered_map<int, int> nums;

    for (int i = 0; i < amo; i++) {
        cin >> num;
        //num = (rand() % 100) + 1;
        auto x = nums.find(num);
        if (x == nums.end()) { nums[num] = 1; }
        else { nums[num]++; }
    }

    int ramo = nums.size();

    long* d = new long[ramo * 4]();
    /*long d[500];
    for (int i = 0; i < 500; i++) { d[i] = 0; }*/

    int i = 0;
    for (auto x = nums.begin(); x != nums.end(); ++x,i++) {
        int ib = i << 2;
        num = x->first;
        d[ib+3] = x->second;
        int ic = ib;
        for (int p = 0; p < 168; p++) {
            prime = primes[p];
            if (num < prime) break;
            b = p & 63;
            if ((num % prime) == 0) { 
                d[ic] |= (1 << b); 
            }
            if (p == 63) { ic++; }
        }

        int jb;
        for (int j = 0; j < i; j++) {
            jb = j << 2;

            if (((d[ib] & d[jb]) == 0) && 
                ((d[ib+1] & d[jb+1]) == 0) && 
                ((d[ib+2] & d[jb+2]) == 0)) { 
                sum+=(d[ib+3]*d[jb+3]); 
            }
        }
    }
    cout << sum << endl;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
3043

user output
3043

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
71 19 26 18 57 78 80 89 31 26 ...

correct output
3086

user output
3086

Test 3

Group: 2, 3

Verdict:

input
100000
66 87 90 67 93 89 57 29 34 4 8...

correct output
3044751906

user output
3044200131

Test 4

Group: 3

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
3039650753

user output
(empty)

Test 5

Group: 3

Verdict:

input
100000
238907 151373 522599 885657 37...

correct output
3031155756

user output
(empty)

Test 6

Group: 3

Verdict: ACCEPTED

input
100000
510510 510510 510510 510510 51...

correct output
0

user output
0

Test 7

Group: 3

Verdict: ACCEPTED

input
100000
999983 999983 999983 999983 99...

correct output
0

user output
0