Submission #846300


Source Code Expand

Copy
#include<iostream>
#include<map>
#include<vector>
using namespace std;

#define MAX 100000
bool f[MAX];
int p[11111],lp;
void init(){
	for(int i=2; i<MAX; i++){
		if(!f[i]){
			p[lp++]=i;
		}
		for(int j=0; j<lp; j++){
			int t=i*p[j];
			if(t>=MAX)break;
			f[t]=true;
			if(i%p[j]==0)break;
		}
	}
}

map<vector<long long int>,int> Map;
int main(){
	init();
	int n;
	cin>>n;
	for(int i=0; i<n; i++){
		long long int x;
		cin>>x;
		vector<long long int> v;
		for(int j=0; j<lp && (long long int)p[j]*p[j]<=x; j++)
			if(x%p[j]==0){
				int z=0;
				while(x%p[j]==0){
					x/=p[j];
					z++;
				}
				z%=3;
				if(z==1)v.push_back(p[j]);else
				if(z==2)v.push_back(-p[j]);
			}
		if(x>1)v.push_back(x);
		Map[v]++;
	}
	vector<long long int> v;
	int res = 0;
	if(Map.count(v)){
		res ++;
		Map.erase(v);
	}
	int res2 = 0;
	for(map<vector<long long int>,int>::iterator it = Map.begin(); it != Map.end(); it++){
		vector<long long int> v1 = it->first;
		int w = it->second;
		for(int i=0; i<v1.size(); i++)
			v1[i] = -v1[i];
		if(Map.count(v1)){
			w = max(w, Map[v1]);
			Map.erase(v1);
		}
		res2 += w;
	}
	cout << res2 + res << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Anticube
User maryanna2016
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1214 Byte
Status TLE
Exec Time 5257 ms
Memory 12032 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 45
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 AC 2372 ms 12032 KB
02.txt AC 2374 ms 12032 KB
03.txt AC 2358 ms 12032 KB
04.txt AC 2346 ms 12032 KB
05.txt AC 2337 ms 12032 KB
06.txt AC 2357 ms 12032 KB
07.txt AC 2328 ms 12032 KB
08.txt AC 2367 ms 12032 KB
09.txt AC 2372 ms 12032 KB
10.txt AC 2327 ms 12032 KB
11.txt TLE 5257 ms 2944 KB
12.txt TLE 5257 ms 2944 KB
13.txt AC 1574 ms 4480 KB
14.txt AC 1603 ms 4480 KB
15.txt AC 1601 ms 4480 KB
16.txt AC 1600 ms 4480 KB
17.txt AC 176 ms 384 KB
18.txt AC 170 ms 384 KB
19.txt AC 170 ms 384 KB
20.txt AC 170 ms 384 KB
21.txt AC 4147 ms 7296 KB
22.txt AC 4134 ms 7168 KB
23.txt AC 4130 ms 7296 KB
24.txt AC 4157 ms 7296 KB
25.txt AC 4214 ms 7168 KB
26.txt AC 4140 ms 7168 KB
27.txt AC 245 ms 9728 KB
28.txt AC 34 ms 384 KB
29.txt AC 48 ms 384 KB
30.txt AC 69 ms 384 KB
31.txt AC 67 ms 384 KB
32.txt AC 67 ms 384 KB
33.txt AC 5 ms 384 KB
34.txt AC 178 ms 384 KB
35.txt AC 149 ms 384 KB
36.txt AC 6 ms 384 KB
37.txt TLE 5257 ms 3456 KB
38.txt TLE 5253 ms 3456 KB
39.txt TLE 5253 ms 3456 KB
40.txt TLE 5253 ms 3456 KB
41.txt AC 5 ms 384 KB
42.txt AC 5 ms 384 KB
43.txt AC 6 ms 384 KB
44.txt AC 5 ms 384 KB
45.txt AC 5 ms 384 KB
46.txt AC 5 ms 384 KB
47.txt AC 5 ms 384 KB
48.txt AC 5 ms 384 KB
s1.txt AC 6 ms 384 KB
s2.txt AC 6 ms 384 KB
s3.txt AC 6 ms 384 KB