Contest Duration: ~ (local time) (110 minutes) Back to Home

Submission #849347

Source Code Expand

Copy
```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector<int> vi;

#define mp make_pair
#define pb push_back

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define endl "\n"

const int MOD = 1000000007;
double PI = 4*atan(1);

vi prime;
vector<pair<ll,ll>> squares;

void genprime() {
FOR(i,2,100001) {
bool f = 0;
F0R(j,prime.size()) {
if (i % prime[j] == 0) {
f = 1;
break;
}
if (prime[j]*prime[j]>i) break;
}
if (!f) {
prime.pb(i);
squares.pb(mp(i,i*i));
}
}
}

pair<ll,ll> fac(ll x) {
ll x1 = 1, x2 = 1, i = 0;
for (;i<prime.size();++i) {
ll t = prime[i]*prime[i]*prime[i];
if (t>x) break;
while (x % t == 0) x /= t;
if (x % prime[i] == 0) {
int c = 0;
while (x % prime[i] == 0) x /= prime[i],x1 *= prime[i],c++;
F0R(j,3-c) x2 *= prime[i];
}
}
pii y = *lower_bound(squares.begin(),squares.end(),mp((ll)0,x));
if (y.s == x)  x2 *= y.f;
else x2 *= (x*x);
return mp(x1*x,x2);
}

map<ll,pair<int,ll>> num;
map<ll,bool> done;

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int N; cin >> N;
genprime();
ll ans = 0;
F0R(i,N) {
ll x; cin >> x;
pair<ll,ll> a = fac(x);
num[a.f].f ++;
num[a.f].s = a.s;
}
for (auto i: num) {
if (done[i.f]) continue;
if (i.s.s == i.f) ans++;
else if (num.find(i.s.s) != num.end()) {
ans += max(num[i.s.s].f,i.s.f);
done[i.s.s] = 1;
} else ans += i.s.f;
}
cout << ans;
}```

#### Submission Info

Submission Time 2016-08-22 11:24:20+0900 D - Anticube Benq C++14 (GCC 5.4.1) 0 1659 Byte WA 5257 ms 13052 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
 AC × 3
 AC × 34 WA × 5 TLE × 12
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 2590 ms 12924 KB
02.txt 2649 ms 12924 KB
03.txt 2637 ms 12924 KB
04.txt 2607 ms 13052 KB
05.txt 2589 ms 12924 KB
06.txt 2605 ms 12924 KB
07.txt 2575 ms 12924 KB
08.txt 2623 ms 12924 KB
09.txt 2600 ms 12924 KB
10.txt 2639 ms 12924 KB
11.txt 5257 ms 1404 KB
12.txt 5257 ms 1404 KB
13.txt 2059 ms 5116 KB
14.txt 2066 ms 5116 KB
15.txt 2080 ms 5116 KB
16.txt 2086 ms 5116 KB
17.txt 88 ms 640 KB
18.txt 88 ms 640 KB
19.txt 88 ms 640 KB
20.txt 89 ms 640 KB
21.txt 5257 ms 3196 KB
22.txt 5257 ms 3196 KB
23.txt 5257 ms 3196 KB
24.txt 5257 ms 3196 KB
25.txt 5257 ms 3196 KB
26.txt 5257 ms 3196 KB
27.txt 219 ms 10876 KB
28.txt 27 ms 640 KB
29.txt 33 ms 640 KB
30.txt 34 ms 640 KB
31.txt 36 ms 640 KB
32.txt 36 ms 640 KB
33.txt 12 ms 640 KB
34.txt 76 ms 640 KB
35.txt 67 ms 640 KB
36.txt 12 ms 640 KB
37.txt 5257 ms 1532 KB
38.txt 5257 ms 1532 KB
39.txt 5257 ms 1532 KB
40.txt 5257 ms 1532 KB
41.txt 12 ms 640 KB
42.txt 12 ms 640 KB
43.txt 12 ms 640 KB
44.txt 12 ms 640 KB
45.txt 12 ms 640 KB
46.txt 12 ms 640 KB
47.txt 12 ms 640 KB
48.txt 12 ms 640 KB
s1.txt 12 ms 640 KB
s2.txt 12 ms 640 KB
s3.txt 12 ms 640 KB