Submission #847735


Source Code Expand

Copy
//In the name of Allah
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 

const int maxN = 1000 * 100 + 100; 
const int mx = 2500 + 10; 

ll a[maxN]; 
map<ll,int> cnt; 
vector<int> pr; 
int mark[maxN]; 

int main() { 
	for( int i = 2 ; i < mx ; i++ ) if( !mark[i] ) { 
		pr.push_back(i); 
		for( int j = i + i ; j < mx; j += i ) 
			mark[j] = true; 
	}
	cerr << pr.size() << endl;

	ios::sync_with_stdio(false); cin.tie(0); 
	int n; cin >> n; 
	for( int i = 0 ; i < n ; i++ ) { 
		cin >> a[i]; 
		for( auto x : pr ) { 
			ll z = x * 1ll * x * x; 
			while( a[i] % z == 0 ) 
				a[i] /= z; 
		}
		cnt[a[i]]++; 
	}
	sort( a , a + n ); 
	int ans = 0; 
	if( cnt[1] ) ans = 1; 
	cnt[1] = 0; 

	for( int i = 0 ; i < n ; i++ ) 
		if( cnt[a[i]] ) { 
			ll x = a[i]; 
			ll z = 1; 
			for( auto y : pr ) 
				if( x % y == 0 ) { 
					int v = 0; 
					while( x % y == 0 ) { 
						v++; 
						x /= y;
					}
					if( v == 1 ) z *= y * 1ll * y; 
					else if( v == 2 ) z *= y; 
					if( x == 1 ) break; 
				} 			
			if( x > 1 ) 
				z *= x * 1ll * x; 
			ans += max( cnt[a[i]] , cnt[z] ); 
			cnt[z] = 0;
			cnt[a[i]] = 0; 
			//cerr << a[i] << "   " << z << " ANS CHANGED TO " << ans << endl;
		}
	cout << ans << endl;
}

Submission Info

Submission Time
Task D - Anticube
User LiTi
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 1294 Byte
Status AC
Exec Time 1489 ms
Memory 13568 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 3
AC × 51
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 AC 1463 ms 13568 KB
02.txt AC 1473 ms 13568 KB
03.txt AC 1469 ms 13568 KB
04.txt AC 1467 ms 13568 KB
05.txt AC 1470 ms 13568 KB
06.txt AC 1470 ms 13568 KB
07.txt AC 1471 ms 13568 KB
08.txt AC 1472 ms 13568 KB
09.txt AC 1470 ms 13568 KB
10.txt AC 1489 ms 13568 KB
11.txt AC 946 ms 4992 KB
12.txt AC 949 ms 4992 KB
13.txt AC 940 ms 4992 KB
14.txt AC 949 ms 4992 KB
15.txt AC 945 ms 4992 KB
16.txt AC 953 ms 4992 KB
17.txt AC 698 ms 1024 KB
18.txt AC 698 ms 1024 KB
19.txt AC 699 ms 1024 KB
20.txt AC 698 ms 1024 KB
21.txt AC 1163 ms 8576 KB
22.txt AC 1162 ms 8576 KB
23.txt AC 1165 ms 8576 KB
24.txt AC 1169 ms 8576 KB
25.txt AC 1160 ms 8576 KB
26.txt AC 1162 ms 8576 KB
27.txt AC 1115 ms 11392 KB
28.txt AC 658 ms 1024 KB
29.txt AC 661 ms 1024 KB
30.txt AC 662 ms 1024 KB
31.txt AC 662 ms 1024 KB
32.txt AC 660 ms 1024 KB
33.txt AC 4 ms 256 KB
34.txt AC 689 ms 1024 KB
35.txt AC 689 ms 1024 KB
36.txt AC 4 ms 256 KB
37.txt AC 996 ms 5888 KB
38.txt AC 1004 ms 5888 KB
39.txt AC 1002 ms 5888 KB
40.txt AC 997 ms 5888 KB
41.txt AC 4 ms 256 KB
42.txt AC 4 ms 256 KB
43.txt AC 4 ms 256 KB
44.txt AC 4 ms 256 KB
45.txt AC 4 ms 256 KB
46.txt AC 4 ms 256 KB
47.txt AC 4 ms 256 KB
48.txt AC 4 ms 256 KB
s1.txt AC 5 ms 256 KB
s2.txt AC 4 ms 256 KB
s3.txt AC 4 ms 256 KB