Submission #1315946


Source Code Expand

#include<bits/stdc++.h>
#include<map>
#define LL long long
#define LD long double
#define INF (1LL<<60)
using namespace std;
map<LL,LL> :: iterator it;
map<LL,LL> F,G;
int n,ans; LL a[100005],p[64],lp;
LL fpc(LL x,LL y,LL mo){ return ((x*y-(LL)((LD)x*y/mo)*mo)%mo+mo)%mo;}
LL fpm(LL x,LL y,LL mo){ LL s=1; while(y){ if(y&1) s=fpc(s,x,mo); y>>=1,x=fpc(x,x,mo);} return s;}
LL gcd(LL x,LL y){ return x ? gcd(y%x,x) : y;}
bool miller_rabin(LL p)
{
	LL a=rand()%(p-1)+1,q=p-1,x,y;
	if(p<=3) return 1;
	while(!a) a=rand()%p;
	for(;(q&1)^1;q>>=1);
	x=fpm(a,q,p);
	for(;q<p-1;q<<=1,x=y){
		y=fpc(x,x,p);
		if(y==1&&x!=1&&x!=p-1) return 0;
	  }
	return x==1;
}
bool test(LL x)
{
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	return 1;
}
LL pollard_rho(LL n)
{
	LL d,c,x,y,a,b;
	for(c=2;;c++){
		y=1,b=a=rand()%n;
		for(x=1;x;x++){
			a=(fpc(a,a,n)+c)%n;
			if(b==a) break;
			d=gcd(abs(b-a),n);
			if(d!=1) return d;
			if(x==y) y<<=1,b=a;
		  }
	  }
	return 0;
}
void divide(LL x)
{
	LL d;
	if(x==1) return ;
	if(x==2){ p[++lp]=2; return ;}
	if(x==4){ p[++lp]=2,p[++lp]=2; return ;}
	if(test(x)){ p[++lp]=x; return ;}
	d=pollard_rho(x);
	divide(d);
	divide(x/d);
}
int main()
{
	int i,k,l,tag=0; LL y,z;
	srand(2222303);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(i=1;i<=n;i++){
		lp=0,divide(a[i]);
		sort(p+1,p+lp+1);
		y=z=1;
		for(k=1;k<=lp;k=l){
			for(l=k;l<=lp&&p[k]==p[l];l++);
			if((l-k)%3==2) y*=p[k]*p[k],z=z>0 ? z*p[k] : -1;
			if((l-k)%3==1){
				y*=p[k];
				if(z>0&&z<=INF/p[k]/p[k]) z*=p[k]*p[k];
				else z=-1;
			  }
		  }
		if(z==-1){ ans++; continue;}
		if(y==1){
			if(!tag) ans++,tag=1;
			continue;
		  }
		F[y]++,G[y]=z;
	  }
	for(it=F.begin();it!=F.end();it++){
		y=G[it->first],z=F[y];
		if(it->second>z||(it->second==z&&it->first>y))
			ans+=it->second;
	  }
	cout<<ans;
	return 0;
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User MemorySlices
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2036 Byte
Status RE
Exec Time 2104 ms
Memory 11392 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:67:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
WA × 1
RE × 1
AC × 1
WA × 6
TLE × 26
RE × 5
Set Name Test Cases
Sample s1.txt, s2.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, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt TLE 2103 ms 1024 KB
02.txt TLE 2103 ms 1024 KB
03.txt TLE 2103 ms 1024 KB
04.txt TLE 2103 ms 1024 KB
05.txt TLE 2103 ms 1024 KB
06.txt TLE 2103 ms 1024 KB
07.txt TLE 2103 ms 1024 KB
08.txt TLE 2103 ms 1024 KB
09.txt TLE 2103 ms 1024 KB
10.txt TLE 2103 ms 1024 KB
11.txt TLE 2103 ms 1024 KB
12.txt TLE 2103 ms 1024 KB
13.txt TLE 2103 ms 1024 KB
14.txt TLE 2103 ms 1024 KB
15.txt TLE 2103 ms 1024 KB
16.txt TLE 2103 ms 1024 KB
17.txt TLE 2103 ms 1024 KB
18.txt TLE 2103 ms 1024 KB
19.txt TLE 2103 ms 1024 KB
20.txt TLE 2103 ms 1024 KB
21.txt TLE 2103 ms 1024 KB
22.txt TLE 2103 ms 1792 KB
23.txt TLE 2103 ms 3840 KB
24.txt TLE 2104 ms 4992 KB
25.txt TLE 2104 ms 4992 KB
26.txt TLE 2104 ms 6528 KB
27.txt RE 907 ms 11392 KB
28.txt WA 1031 ms 1024 KB
29.txt WA 1036 ms 1024 KB
30.txt RE 789 ms 1024 KB
31.txt AC 1 ms 256 KB
32.txt RE 133 ms 256 KB
33.txt WA 1 ms 256 KB
34.txt RE 135 ms 256 KB
35.txt WA 1 ms 256 KB
36.txt WA 1 ms 256 KB
s1.txt RE 99 ms 256 KB
s2.txt WA 1 ms 256 KB