Submission #2100130
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=105,M=1e7+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 |
2133 ms |
Memory |
296320 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 |
4 ms |
16512 KB |
0_01.txt |
AC |
4 ms |
16512 KB |
0_02.txt |
AC |
73 ms |
24704 KB |
1_00.txt |
AC |
4 ms |
16512 KB |
1_01.txt |
AC |
4 ms |
16512 KB |
1_02.txt |
AC |
4 ms |
16512 KB |
1_03.txt |
RE |
543 ms |
279936 KB |
1_04.txt |
RE |
247 ms |
279040 KB |
1_05.txt |
RE |
247 ms |
279040 KB |
1_06.txt |
AC |
4 ms |
16512 KB |
1_07.txt |
RE |
373 ms |
296320 KB |
1_08.txt |
RE |
411 ms |
296320 KB |
1_09.txt |
RE |
418 ms |
296064 KB |
1_10.txt |
RE |
406 ms |
295808 KB |
1_11.txt |
RE |
363 ms |
295552 KB |
1_12.txt |
RE |
326 ms |
295424 KB |
1_13.txt |
RE |
332 ms |
295424 KB |
1_14.txt |
RE |
401 ms |
295168 KB |
1_15.txt |
RE |
323 ms |
295168 KB |
1_16.txt |
RE |
355 ms |
295296 KB |
1_17.txt |
RE |
321 ms |
295168 KB |
1_18.txt |
RE |
372 ms |
295168 KB |
1_19.txt |
RE |
372 ms |
295168 KB |
1_20.txt |
RE |
511 ms |
293120 KB |
1_21.txt |
RE |
320 ms |
295040 KB |
1_22.txt |
RE |
523 ms |
295040 KB |
1_23.txt |
RE |
315 ms |
295040 KB |
1_24.txt |
RE |
319 ms |
295040 KB |
1_25.txt |
RE |
409 ms |
292992 KB |
1_26.txt |
RE |
296 ms |
290944 KB |
1_27.txt |
WA |
51 ms |
30848 KB |
1_28.txt |
RE |
310 ms |
288896 KB |
1_29.txt |
RE |
348 ms |
290944 KB |
1_30.txt |
RE |
349 ms |
286848 KB |
1_31.txt |
RE |
583 ms |
292992 KB |
1_32.txt |
RE |
319 ms |
292992 KB |
1_33.txt |
AC |
68 ms |
24704 KB |
1_34.txt |
RE |
314 ms |
290944 KB |
1_35.txt |
AC |
58 ms |
28800 KB |
1_36.txt |
AC |
29 ms |
20608 KB |
1_37.txt |
WA |
52 ms |
28800 KB |
1_38.txt |
RE |
291 ms |
288896 KB |
1_39.txt |
WA |
51 ms |
28800 KB |
1_40.txt |
RE |
353 ms |
296320 KB |
1_41.txt |
RE |
443 ms |
296320 KB |
1_42.txt |
RE |
409 ms |
296320 KB |
1_43.txt |
RE |
351 ms |
296320 KB |
1_44.txt |
RE |
374 ms |
296320 KB |
1_45.txt |
RE |
359 ms |
296320 KB |
1_46.txt |
RE |
358 ms |
296320 KB |
1_47.txt |
RE |
351 ms |
296320 KB |
1_48.txt |
RE |
332 ms |
296320 KB |
1_49.txt |
RE |
345 ms |
296320 KB |
1_50.txt |
RE |
355 ms |
296320 KB |
1_51.txt |
RE |
1659 ms |
296192 KB |
1_52.txt |
RE |
355 ms |
296320 KB |
1_53.txt |
RE |
355 ms |
296320 KB |
1_54.txt |
RE |
429 ms |
296320 KB |
1_55.txt |
RE |
377 ms |
296320 KB |
1_56.txt |
RE |
682 ms |
295040 KB |
1_57.txt |
RE |
1497 ms |
295040 KB |
1_58.txt |
RE |
337 ms |
295168 KB |
1_59.txt |
RE |
367 ms |
295040 KB |
1_60.txt |
TLE |
2116 ms |
249472 KB |
1_61.txt |
RE |
328 ms |
295168 KB |
1_62.txt |
RE |
758 ms |
295040 KB |
1_63.txt |
RE |
508 ms |
295040 KB |
1_64.txt |
RE |
922 ms |
295040 KB |
1_65.txt |
RE |
1016 ms |
295040 KB |
1_66.txt |
RE |
868 ms |
295168 KB |
1_67.txt |
TLE |
2133 ms |
295168 KB |
1_68.txt |
RE |
527 ms |
295040 KB |
1_69.txt |
RE |
1732 ms |
295168 KB |
1_70.txt |
RE |
789 ms |
295040 KB |
1_71.txt |
RE |
507 ms |
295168 KB |