CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Tekijät
Sender:tsiki2
Submission time:2020-11-09 02:15:42 +0200
Language:C++ (C++11)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.02 s1, 2, 3details
#3--2, 3details
#4--3details
#5--3details
#6--3details
#7--3details

Compiler report

input/code.cpp: In function 'std::vector<int> primes(int)':
input/code.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:46:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     return ans;
     ^~~~~~
input/code.cpp: In function 'std::vector<int> uprimes(int)':
input/code.cpp:67:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:69:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     return ans;
     ^~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nums.size(); i++) {
                  ~~^~~~~~~~~~~~~
input/code.cpp:122:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; pi <...

Code

#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long LL;
#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;
// g++ -Wall -Wshadow -std=c++11 a.cpp && ./a.out
vector<int> primes(int n) {
vector<int> ans;
while (n % 2 == 0) {
ans.push_back(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0)
{
ans.push_back(i);
n = n/i;
}
}
if (n > 2)
ans.push_back(n);
return ans;
}
vector<int> uprimes(int n) {
vector<int> ans;
while (n % 2 == 0) {
if ((ans.size() && ans.back() != 2) || ans.size() == 0)
ans.push_back(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0)
{
if ((ans.size() && ans.back() != i) || ans.size() == 0)
ans.push_back(i);
// ans.push_back(i);
n = n/i;
}
}
if (n > 2)
ans.push_back(n);
return ans;
}
bool isprime(int n) {
vector<int> ans;
for (int i = 2; i <= sqrt(n); i = i + 2) {
if (n % i == 0)
{
return false;
}
}
return true;
}
int PLIM = 1000;
int main() {
std::ios::sync_with_stdio(false);cin.tie(0);
int n; cin>>n;
int maxnum = 0;
vector<int> nums;
vector<int> numcnt(1000001);
vector<int> numidx(1000001, -1);
map<int,vector<int>> m;
LL ans = 0;
LL ones = 0;
for (int i =0;i<n; i++) {
int nn; cin>>nn;
if (nn == 1) {
ones++;
continue;
}
maxnum = max(nn, maxnum);
numidx[nn] = nums.size();
nums.push_back(nn);
}
sort(nums.begin(), nums.end());
ans += ones * nums.size() + ones*(ones-1)/2;
vector<int> primes_under_lim;
vector<int> prime_to_idx(PLIM + 1);
for (int i = 2; i <= PLIM; i++) {
if (isprime(i)) {
prime_to_idx[i] = primes_under_lim.size();
primes_under_lim.push_back(i);
}
}
vector<bitset<100000>> bitsets(primes_under_lim.size());
bitset<100000> tmp;
for (int i = 0; i < nums.size(); i++) {
auto asd = uprimes(nums[i]);
int pi = 0;
for (; pi < asd.size() && asd[pi] < PLIM; pi++) {
int idx = prime_to_idx[asd[pi]];
bitsets[idx].set(i);
tmp |= bitsets[idx];
}
int out = tmp.count() - 1;
out = max(0, out);
for (; pi < asd.size(); pi++) {
for (auto idxx : m[asd[pi]]) {
if (!tmp[idxx]) {
out++;
}
}
m[asd[pi]].push_back(i);
// int zxc = nums[i] - asd[pi];
// while (zxc > 0) {
// if (numcnt[zxc] && !tmp[numidx[zxc]]) {
// out += numcnt[zxc];
// }
// zxc -= asd[pi];
// }
}
numcnt[nums[i]]++;
int add = i-out;
ans += add;
tmp.reset();
}
cout << ans << 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
(empty)

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:

input
100000
510510 510510 510510 510510 51...

correct output
0

user output
(empty)

Test 7

Group: 3

Verdict:

input
100000
999983 999983 999983 999983 99...

correct output
0

user output
(empty)