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
Task D - Anticube
User Benq
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1431 Byte
Status
Exec Time 5254 ms
Memory 13056 KB

Test Cases

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