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

Submission #1046142

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

vector<ll> prime;
unordered_map<ll,ll> square;

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);
}
}

pair<ll,ll> fac(ll x) {
ll x1 = 1, x2 = 1;
F0R(i,prime.size()) {
int c = 0;
while (x % prime[i] == 0) c++, x /= prime[i];
c %= 3;
if (c == 1) x1 *= prime[i], x2 *= (prime[i]*prime[i]);
else if (c == 2) x1 *= (prime[i]*prime[i]), x2 *= prime[i];
if ((prime[i]*prime[i]*prime[i])>x) break;
}
if (square.find(x) == square.end()) x1 *= x, x2 *= (x*x);
else x1 *= x, x2 *= square[x];
return mp(x1,x2);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
map<pair<ll,ll>,ll> num;
map<ll,bool> done;

int N; cin >> N;
genprime();
for (ll i: prime) square[i*i] = i;
F0R(i,N) {
ll x; cin >> x;
num[fac(x)]++;
}

ll ans = 0;
for (auto i: num) {
if (done[i.f.f]) continue;
if (i.f.f == i.f.s) ans++;
else if (num.find(mp(i.f.s,i.f.f)) != num.end()) {
ans += max(num[mp(i.f.s,i.f.f)],i.s);
done[i.f.s] = 1;
} else ans += i.s;
}
cout << ans;
}```

#### Submission Info

Submission Time 2016-12-27 07:38:01+0900 D - Anticube Benq C++14 (GCC 5.4.1) 1100 1480 Byte AC 340 ms 13312 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 1100 / 1100 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 218 ms 13312 KB
02.txt 219 ms 13312 KB
03.txt 219 ms 13312 KB
04.txt 217 ms 13312 KB
05.txt 221 ms 13312 KB
06.txt 218 ms 13312 KB
07.txt 217 ms 13312 KB
08.txt 220 ms 13312 KB
09.txt 218 ms 13312 KB
10.txt 219 ms 13312 KB
11.txt 340 ms 4608 KB
12.txt 340 ms 4608 KB
13.txt 110 ms 5376 KB
14.txt 111 ms 5376 KB
15.txt 111 ms 5376 KB
16.txt 110 ms 5376 KB
17.txt 67 ms 768 KB
18.txt 67 ms 768 KB
19.txt 67 ms 768 KB
20.txt 67 ms 768 KB
21.txt 195 ms 8448 KB
22.txt 194 ms 8320 KB
23.txt 194 ms 8448 KB
24.txt 194 ms 8448 KB
25.txt 195 ms 8320 KB
26.txt 194 ms 8320 KB
27.txt 101 ms 11136 KB
28.txt 21 ms 768 KB
29.txt 27 ms 768 KB
30.txt 29 ms 768 KB
31.txt 27 ms 768 KB
32.txt 27 ms 768 KB
33.txt 12 ms 768 KB
34.txt 68 ms 768 KB
35.txt 64 ms 768 KB
36.txt 13 ms 768 KB
37.txt 316 ms 5632 KB
38.txt 317 ms 5632 KB
39.txt 315 ms 5632 KB
40.txt 316 ms 5632 KB
41.txt 13 ms 768 KB
42.txt 13 ms 768 KB
43.txt 12 ms 768 KB
44.txt 13 ms 768 KB
45.txt 13 ms 768 KB
46.txt 12 ms 768 KB
47.txt 13 ms 768 KB
48.txt 13 ms 768 KB
s1.txt 13 ms 768 KB
s2.txt 12 ms 768 KB
s3.txt 12 ms 768 KB