Submission #847499


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

pair<ll,ll> fac(ll x) {
	ll x1 = 1, x2 = 1, i = 2;
	for (;;++i) {
		if (i*i*i>x) break;
		while (x % (i*i*i) == 0) x /= (i*i*i);
		if (x % i == 0) {
			int c = 0;
			while (x % i == 0) x /= i,x1 *= i,c++;
			F0R(j,3-c) x2 *= i;
		}
	}
	for (;;++i) {
		if (i*i>x) break;
		if (x % i == 0) {
			int c = 0;
			while (x % i == 0) x /= i, x1 *= i,c++;
			F0R(j,3-c) x2 *= i;
		}
	}
	if (x>1) x2 *= (x*x);
	return mp(x*x1,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;
	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;
		// cout << x << " " << num[a.f].s << "\n";
	}
	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
Task D - Anticube
User Benq
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1386 Byte
Status
Exec Time 5254 ms
Memory 10624 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 0 / 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 5254 ms 2176 KB
02.txt 5253 ms 2048 KB
03.txt 5253 ms 2048 KB
04.txt 5253 ms 2176 KB
05.txt 5253 ms 2176 KB
06.txt 5253 ms 2048 KB
07.txt 5253 ms 2176 KB
08.txt 5253 ms 2048 KB
09.txt 5253 ms 2048 KB
10.txt 5253 ms 2176 KB
11.txt 5253 ms 512 KB
12.txt 5253 ms 512 KB
13.txt 5253 ms 1792 KB
14.txt 5253 ms 1792 KB
15.txt 5253 ms 1920 KB
16.txt 5253 ms 1792 KB
17.txt 83 ms 256 KB
18.txt 83 ms 256 KB
19.txt 83 ms 256 KB
20.txt 83 ms 256 KB
21.txt 5253 ms 896 KB
22.txt 5253 ms 896 KB
23.txt 5253 ms 896 KB
24.txt 5253 ms 896 KB
25.txt 5253 ms 896 KB
26.txt 5253 ms 896 KB
27.txt 315 ms 10624 KB
28.txt 14 ms 256 KB
29.txt 21 ms 256 KB
30.txt 30 ms 256 KB
31.txt 28 ms 256 KB
32.txt 28 ms 256 KB
33.txt 4 ms 256 KB
34.txt 65 ms 256 KB
35.txt 57 ms 256 KB
36.txt 4 ms 256 KB
37.txt 5253 ms 512 KB
38.txt 5253 ms 640 KB
39.txt 5253 ms 512 KB
40.txt 5253 ms 512 KB
41.txt 4 ms 256 KB
42.txt 4 ms 256 KB
43.txt 5 ms 256 KB
44.txt 4 ms 256 KB
45.txt 4 ms 256 KB
46.txt 4 ms 256 KB
47.txt 4 ms 256 KB
48.txt 4 ms 256 KB
s1.txt 4 ms 256 KB
s2.txt 4 ms 256 KB
s3.txt 5 ms 256 KB