Submission #1837846


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <ctime>
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll,ll> abcd;

const int N=100010;

int n,p[N];
ll a[N],b[N],c[N];
map<ll,int> vis,ct,sqrt;

inline void Pre(){
  for(int i=2;i<=100000;i++){
    if(!p[i]) p[++*p]=i;
    for(int j=1;j<=*p && 1LL*p[j]*i<=100000;i++){
      p[p[j]*i]=1; if(i%p[j]==0) break;
    }
  }
  for(int i=1;i<=*p;i++) sqrt[1LL*p[i]*p[i]]=p[i];
}

vector<abcd> v;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void read(ll &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void read(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

int ans;

inline void work(int i){
  b[i]=1; c[i]=1;
  for(int j=1;j<=*p && 1LL*p[j]*p[j]<=a[i] && p[j]<=2200;j++)
    if(a[i]%p[j]==0){
      int cnt=0; while(a[i]%p[j]==0) a[i]/=p[j],cnt++;
      cnt%=3; for(int k=1;k<=cnt;k++) c[i]*=p[j];
      if(cnt)
	for(int k=cnt+1;k<=3;k++){
	  b[i]*=p[j];
	  if(b[i]>10000000000LL) return ans++,void();
	}
    }
  if(sqrt[a[i]]){
    c[i]*=sqrt[a[i]];
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
  }
  else{
    c[i]*=a[i];
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
  }
  if(c[i]==1){
    if(!ct[1]) ans++; ct[1]=1; return ;
  }
  ct[c[i]]++;
  v.pb(abcd(c[i],b[i]));
}

int main(){
  read(n); Pre();
  for(int i=1;i<=n;i++) {
    read(a[i]),work(i);
  }
  vis[1]=1;
  for(int i=0;i<v.size();i++){
    if(vis[v[i].fi]) continue;
    vis[v[i].fi]=vis[v[i].se]=1;
    ans+=max(ct[v[i].fi],ct[v[i].se]);
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Submission Time
Task D - Anticube
User SBP
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2006 Byte
Status WA
Exec Time 1349 ms
Memory 28912 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 37
WA × 14
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 937 ms 12160 KB
02.txt AC 944 ms 12160 KB
03.txt AC 940 ms 12160 KB
04.txt AC 939 ms 12160 KB
05.txt AC 936 ms 12176 KB
06.txt AC 936 ms 12160 KB
07.txt AC 933 ms 12160 KB
08.txt AC 937 ms 12160 KB
09.txt AC 940 ms 12160 KB
10.txt AC 940 ms 12160 KB
11.txt AC 1349 ms 11636 KB
12.txt AC 1339 ms 11636 KB
13.txt WA 460 ms 10744 KB
14.txt WA 463 ms 10744 KB
15.txt WA 464 ms 10872 KB
16.txt WA 464 ms 10744 KB
17.txt AC 74 ms 7792 KB
18.txt AC 72 ms 7792 KB
19.txt AC 74 ms 7792 KB
20.txt AC 73 ms 7792 KB
21.txt WA 711 ms 13300 KB
22.txt WA 710 ms 13300 KB
23.txt WA 708 ms 13300 KB
24.txt WA 722 ms 13172 KB
25.txt WA 718 ms 13300 KB
26.txt WA 707 ms 13300 KB
27.txt AC 164 ms 28912 KB
28.txt AC 22 ms 6144 KB
29.txt AC 29 ms 6144 KB
30.txt AC 33 ms 7920 KB
31.txt AC 31 ms 7920 KB
32.txt AC 31 ms 7920 KB
33.txt AC 15 ms 3712 KB
34.txt AC 68 ms 7920 KB
35.txt AC 63 ms 6144 KB
36.txt AC 15 ms 3712 KB
37.txt WA 1218 ms 12280 KB
38.txt WA 1220 ms 12276 KB
39.txt WA 1218 ms 12276 KB
40.txt WA 1218 ms 12276 KB
41.txt AC 16 ms 3712 KB
42.txt AC 15 ms 3712 KB
43.txt AC 15 ms 3712 KB
44.txt AC 15 ms 3712 KB
45.txt AC 15 ms 3712 KB
46.txt AC 15 ms 3712 KB
47.txt AC 15 ms 3712 KB
48.txt AC 16 ms 3712 KB
s1.txt AC 15 ms 3712 KB
s2.txt AC 15 ms 3712 KB
s3.txt AC 15 ms 3712 KB