CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Tekijät
Sender:tsiki2
Submission time:2020-11-08 23:55:11 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'std::vector<int> primes(int)':
input/code.cpp:43:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:45: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:66:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:68: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:111:9: error: 'bitset' was not declared in this scope
  vector<bitset<100000>> bitsets(primes_under_1k.size());
         ^~~~~~
input/code.cpp:111:9: note: suggested alternative: 'fd_set'
  vector<bitset<100000>> bitsets(primes_under_1k.size());
         ^~~~~~
         fd_set
input/code.cpp...

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>
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 BITSET_SZ = 100000;
int main() {
std::ios::sync_with_stdio(false);cin.tie(0);
int n; cin>>n;
vector<int> nums;
vector<int> numcnt(1000001);
LL ans = 0;
LL ones = 0;
for (int i =0;i<n; i++) {
int nn; cin>>nn;
if (nn == 1) {
ones++;
continue;
}
nums.push_back(nn);
}
sort(nums.begin(), nums.end());
ans += ones * nums.size() + ones*(ones-1)/2;
vector<int> primes_under_1k;
vector<int> prime_to_idx(1000);
for (int i = 2; i <= 1000; i++) {
if (isprime(i)) {
primes_under_1k.push_back(i);
prime_to_idx[i] = primes_under_1k.size();
}
}
vector<bitset<100000>> bitsets(primes_under_1k.size());
for (int i = 0; i < nums.size(); i++) {
auto asd = uprimes(nums[i]);
bitset<100000> tmp;
int pi = 0;
for (; pi < asd.size() && asd[pi] < 1000; pi++) {
int idx = prime_to_idx[asd[pi]];
bitsets[idx].set(i);
tmp |= bitsets[idx];
}
int out = tmp.count() - 1;
for (; pi < asd.size(); pi++) {
int zxc = asd[pi];
while (zxc <= 1000000) {
if (numcnt[zxc]) {
for (int p : asd) {
if ((zxc % p)==0) {
out += numcnt[zxc];
}
}
}
zxc += asd[pi];
}
}
// cout << out << " isout " << nums[i] << " " << ans << endl;
numcnt[nums[i]]++;
int add = i-out;
ans += add;
}
cout << ans << endl;
// cout << test.size() << endl;
// for (int i =0;i<n;i++) {
// cin>>a[i];
// nums.insert(a[i]);
// }
// sort(a.begin(), a.end());
// LL ans = 0;
// for (int i=0;i<n;i++) {
// vector<int> ps = primes(a[i]);
// }
}