Submission #2100156
Source Code Expand
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,u,v) for(int i=BB[u],v=B[BB[u]][1];i;v=B[i=B[i][0]][1])
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
char ch;
int read(){int n=0,p=1;for(ch=getchar();ch<'0' || '9'<ch;ch=getchar())if(ch=='-') p=-1;for(;'0'<=ch && ch<='9';ch=getchar()) n=n*10+ch-'0';return n*p;}
const int N=205,M=2e7+5;
int n,m,a[N],d[N<<1],pr[M];
bool b[M],c[M],bz[M];
void prep()
{
mset(bz,1);
bz[0]=bz[1]=0;
fo(i,2,m)
{
if(bz[i]) pr[++pr[0]]=i;
fo(j,1,pr[0])
{
ll x=(ll)i*pr[j];
if(x>m) break;
bz[x]=0;
if(i%pr[j]==0) break;
}
}
}
const int V=N<<2,INF=1e9;
const int E=4*V*V;
int ans,B0,S,T,BB[V],dis[V],B[E][4];
bool vis[V];
void link(int u,int v,int r,int w)
{
B[++B0][1]=v,B[B0][2]=r,B[B0][3]=w,B[B0][0]=BB[u],BB[u]=B0;
if(!(B0&1)) link(v,u,0,-w);
}
int aug(int v,int flow)
{
vis[v]=1;
if(v==T)
{
ans+=dis[S]*flow;
return flow;
}
efo(i,v,u)
if(B[i][2] && dis[v]==dis[u]+B[i][3])
{
int f=aug(u,min(flow,B[i][2]));
if(f)
{
B[i][2]-=f,B[i^1][2]+=f;
return f;
}
}
return 0;
}
bool change()
{
int minh=INF;
fo(u,S,T) if(vis[u])
efo(i,u,v) if(!vis[v])
if(B[i][2]) minh=min(minh,dis[u]+B[i][3]-dis[v]);
if(minh==INF) return 0;
fo(i,S,T) if(vis[i]) dis[i]+=minh;
return 1;
}
int main()
{
n=read();
fo(i,1,n) b[a[i]=read()]=1,m=max(m,a[i]);
++m;
prep();
fo(i,1,m) c[i]=b[i]^b[i-1];
fo(i,1,m) if(c[i]) d[++d[0]]=i;
B0=1,S=0,T=d[0]+d[0]+1;
fo(i,1,d[0]-1)
fo(j,i+1,d[0])
{
if((d[j]-d[i])%2==0) link(i,d[0]+j,1,2),link(j,d[0]+i,1,2);
else
if(bz[d[j]-d[i]]) link(i,d[0]+j,1,1),link(j,d[0]+i,1,1);
else link(i,d[0]+j,1,3),link(j,d[0]+i,1,3);
}
fo(i,1,d[0]) link(S,i,1,0),link(d[0]+i,T,1,0);
do
{
while(aug(S,INF)) mset(vis,0);
}
while(change());
printf("%d",ans/2);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Prime Flip |
User |
cervol |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2035 Byte |
Status |
RE |
Exec Time |
2141 ms |
Memory |
310656 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1200 |
Status |
|
AC |
× 10 |
WA |
× 3 |
TLE |
× 2 |
RE |
× 60 |
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
7 ms |
26752 KB |
0_01.txt |
AC |
7 ms |
26752 KB |
0_02.txt |
AC |
77 ms |
39040 KB |
1_00.txt |
AC |
7 ms |
26752 KB |
1_01.txt |
AC |
7 ms |
26752 KB |
1_02.txt |
AC |
7 ms |
26752 KB |
1_03.txt |
RE |
419 ms |
290176 KB |
1_04.txt |
RE |
249 ms |
289280 KB |
1_05.txt |
RE |
250 ms |
289280 KB |
1_06.txt |
AC |
7 ms |
26752 KB |
1_07.txt |
RE |
371 ms |
310656 KB |
1_08.txt |
RE |
415 ms |
310656 KB |
1_09.txt |
RE |
421 ms |
310400 KB |
1_10.txt |
RE |
409 ms |
310144 KB |
1_11.txt |
RE |
367 ms |
309888 KB |
1_12.txt |
RE |
329 ms |
309760 KB |
1_13.txt |
RE |
337 ms |
309760 KB |
1_14.txt |
RE |
406 ms |
309504 KB |
1_15.txt |
RE |
327 ms |
307456 KB |
1_16.txt |
RE |
362 ms |
309632 KB |
1_17.txt |
RE |
324 ms |
307456 KB |
1_18.txt |
RE |
376 ms |
309504 KB |
1_19.txt |
RE |
377 ms |
309504 KB |
1_20.txt |
RE |
516 ms |
309504 KB |
1_21.txt |
RE |
324 ms |
309376 KB |
1_22.txt |
RE |
525 ms |
305280 KB |
1_23.txt |
RE |
319 ms |
307328 KB |
1_24.txt |
RE |
324 ms |
307328 KB |
1_25.txt |
RE |
413 ms |
305280 KB |
1_26.txt |
RE |
299 ms |
301184 KB |
1_27.txt |
WA |
53 ms |
36992 KB |
1_28.txt |
RE |
314 ms |
301184 KB |
1_29.txt |
RE |
354 ms |
303232 KB |
1_30.txt |
RE |
352 ms |
299136 KB |
1_31.txt |
RE |
585 ms |
303232 KB |
1_32.txt |
RE |
322 ms |
305280 KB |
1_33.txt |
AC |
71 ms |
36992 KB |
1_34.txt |
RE |
319 ms |
303232 KB |
1_35.txt |
AC |
60 ms |
39040 KB |
1_36.txt |
AC |
31 ms |
28800 KB |
1_37.txt |
WA |
54 ms |
36992 KB |
1_38.txt |
RE |
293 ms |
297088 KB |
1_39.txt |
WA |
53 ms |
34944 KB |
1_40.txt |
RE |
355 ms |
310656 KB |
1_41.txt |
RE |
444 ms |
310656 KB |
1_42.txt |
RE |
411 ms |
310656 KB |
1_43.txt |
RE |
353 ms |
310656 KB |
1_44.txt |
RE |
379 ms |
310656 KB |
1_45.txt |
RE |
361 ms |
310656 KB |
1_46.txt |
RE |
363 ms |
310656 KB |
1_47.txt |
RE |
357 ms |
310656 KB |
1_48.txt |
RE |
336 ms |
310656 KB |
1_49.txt |
RE |
348 ms |
310656 KB |
1_50.txt |
RE |
358 ms |
310656 KB |
1_51.txt |
RE |
1662 ms |
310528 KB |
1_52.txt |
RE |
357 ms |
310656 KB |
1_53.txt |
RE |
357 ms |
310656 KB |
1_54.txt |
RE |
432 ms |
310656 KB |
1_55.txt |
RE |
379 ms |
310656 KB |
1_56.txt |
RE |
687 ms |
309504 KB |
1_57.txt |
RE |
1498 ms |
309504 KB |
1_58.txt |
RE |
342 ms |
309504 KB |
1_59.txt |
RE |
370 ms |
309504 KB |
1_60.txt |
TLE |
2116 ms |
259840 KB |
1_61.txt |
RE |
331 ms |
307456 KB |
1_62.txt |
RE |
760 ms |
307328 KB |
1_63.txt |
RE |
511 ms |
307456 KB |
1_64.txt |
RE |
929 ms |
309504 KB |
1_65.txt |
RE |
1018 ms |
307456 KB |
1_66.txt |
RE |
872 ms |
307456 KB |
1_67.txt |
TLE |
2141 ms |
309504 KB |
1_68.txt |
RE |
530 ms |
309504 KB |
1_69.txt |
RE |
1721 ms |
309504 KB |
1_70.txt |
RE |
794 ms |
309376 KB |
1_71.txt |
RE |
512 ms |
309504 KB |