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

Submission #1046129

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, 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), square.pb(i*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 *= square[i];
else if (c == 2) x1 *= square[i], x2 *= prime[i];
if (square[i]>x) break;
}
x1 *= x, x2 *= (x*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();
// cout << prime.size() << "\n";

F0R(i,N) {
ll x; cin >> x;
// cout << x << " " << fac(x).f << " " << fac(x).s << "\n";
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:09:56+0900 D - Anticube Benq C++14 (GCC 5.4.1) 0 1431 Byte WA 5254 ms 13056 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
 AC × 3
 AC × 35 WA × 10 TLE × 6
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 1525 ms 12928 KB
02.txt 1555 ms 13056 KB
03.txt 1541 ms 12928 KB
04.txt 1526 ms 12928 KB
05.txt 1513 ms 12928 KB
06.txt 1524 ms 12928 KB
07.txt 1507 ms 12928 KB
08.txt 1529 ms 12928 KB
09.txt 1530 ms 12928 KB
10.txt 1520 ms 12928 KB
11.txt 5254 ms 2176 KB
12.txt 5254 ms 2176 KB
13.txt 946 ms 5120 KB
14.txt 964 ms 5120 KB
15.txt 970 ms 5120 KB
16.txt 966 ms 5120 KB
17.txt 67 ms 512 KB
18.txt 67 ms 512 KB
19.txt 67 ms 512 KB
20.txt 67 ms 512 KB
21.txt 2935 ms 8064 KB
22.txt 2922 ms 8064 KB
23.txt 2909 ms 8064 KB
24.txt 2913 ms 8064 KB
25.txt 2935 ms 8064 KB
26.txt 2923 ms 8064 KB
27.txt 112 ms 10880 KB
28.txt 18 ms 640 KB
29.txt 24 ms 512 KB
30.txt 26 ms 512 KB
31.txt 25 ms 512 KB
32.txt 25 ms 512 KB
33.txt 12 ms 512 KB
34.txt 67 ms 512 KB
35.txt 62 ms 512 KB
36.txt 12 ms 640 KB
37.txt 5254 ms 2432 KB
38.txt 5254 ms 2432 KB
39.txt 5254 ms 2432 KB
40.txt 5254 ms 2560 KB
41.txt 12 ms 512 KB
42.txt 11 ms 512 KB
43.txt 12 ms 512 KB
44.txt 11 ms 512 KB
45.txt 12 ms 512 KB
46.txt 12 ms 512 KB
47.txt 11 ms 512 KB
48.txt 12 ms 512 KB
s1.txt 12 ms 512 KB
s2.txt 12 ms 512 KB
s3.txt 12 ms 512 KB