# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

18642 | 2016-02-13T07:58:02 Z | Namnamseo | 경비원 (GA8_guard) | C++14 | 406 ms | 1364 KB |

#include <cstdio> #include <algorithm> #include <queue> int ps[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; int pn=15; int n; int data[2223]; typedef std::pair<int,int> pp; pp dd[2223]; int dp [1<<15]; int dptmp[1<<15]; int M=int(1e9)+7; bool isprime(int x){ for(int i=2;i*i<=x;++i) if(x%i==0) return 0; return 1; } int getMaxDivisor(int x){ for(int i=x;i>=1;--i) if(x%i==0 && isprime(i)) return i; return '?'; } int main() { int i,j; scanf("%d",&n); for(i=0;i<n;++i){ scanf("%d",data+i); dd[i]={getMaxDivisor(data[i]),data[i]}; } std::sort(dd,dd+n); dp [0]=1; dptmp[0]=1; for(i=0;i<n;++i){ int mymask = 0; int myval = dd[i].second; for(j=0; j<pn; ++j) if(myval % ps[j]==0) mymask |= (1<<j); for(j=0; j<32768; ++j){ if((j&mymask) == mymask){ dptmp[j]+=dp[j^mymask]; dptmp[j]%=M; } } if(i+1==n || dd[i].first<=47 || dd[i].first != dd[i+1].first){ for(j=0; j<32768; ++j) dp[j]=dptmp[j]; } } int ans=0; for(i=0; i<32768; ++i) ans+=dp[i], ans%=M; printf("%d\n",(ans-n-1+M)%M); return 0; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 1364 KB | Output is correct |

2 | Correct | 0 ms | 1364 KB | Output is correct |

3 | Correct | 0 ms | 1364 KB | Output is correct |

4 | Correct | 1 ms | 1364 KB | Output is correct |

5 | Correct | 0 ms | 1364 KB | Output is correct |

6 | Correct | 0 ms | 1364 KB | Output is correct |

7 | Correct | 2 ms | 1364 KB | Output is correct |

8 | Correct | 0 ms | 1364 KB | Output is correct |

9 | Correct | 3 ms | 1364 KB | Output is correct |

10 | Correct | 2 ms | 1364 KB | Output is correct |

11 | Correct | 3 ms | 1364 KB | Output is correct |

12 | Correct | 0 ms | 1364 KB | Output is correct |

13 | Correct | 0 ms | 1364 KB | Output is correct |

14 | Correct | 0 ms | 1364 KB | Output is correct |

15 | Correct | 0 ms | 1364 KB | Output is correct |

16 | Correct | 0 ms | 1364 KB | Output is correct |

17 | Correct | 0 ms | 1364 KB | Output is correct |

18 | Correct | 1 ms | 1364 KB | Output is correct |

19 | Correct | 0 ms | 1364 KB | Output is correct |

20 | Correct | 0 ms | 1364 KB | Output is correct |

21 | Correct | 0 ms | 1364 KB | Output is correct |

22 | Correct | 0 ms | 1364 KB | Output is correct |

23 | Correct | 2 ms | 1364 KB | Output is correct |

24 | Correct | 0 ms | 1364 KB | Output is correct |

25 | Correct | 0 ms | 1364 KB | Output is correct |

26 | Correct | 3 ms | 1364 KB | Output is correct |

27 | Correct | 4 ms | 1364 KB | Output is correct |

28 | Correct | 3 ms | 1364 KB | Output is correct |

29 | Correct | 4 ms | 1364 KB | Output is correct |

30 | Correct | 5 ms | 1364 KB | Output is correct |

31 | Correct | 0 ms | 1364 KB | Output is correct |

32 | Correct | 1 ms | 1364 KB | Output is correct |

33 | Correct | 1 ms | 1364 KB | Output is correct |

34 | Correct | 2 ms | 1364 KB | Output is correct |

35 | Correct | 0 ms | 1364 KB | Output is correct |

36 | Correct | 0 ms | 1364 KB | Output is correct |

37 | Correct | 1 ms | 1364 KB | Output is correct |

38 | Correct | 0 ms | 1364 KB | Output is correct |

39 | Correct | 0 ms | 1364 KB | Output is correct |

40 | Correct | 2 ms | 1364 KB | Output is correct |

41 | Correct | 3 ms | 1364 KB | Output is correct |

42 | Correct | 3 ms | 1364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 1364 KB | Output is correct |

2 | Correct | 0 ms | 1364 KB | Output is correct |

3 | Correct | 1 ms | 1364 KB | Output is correct |

4 | Correct | 0 ms | 1364 KB | Output is correct |

5 | Correct | 0 ms | 1364 KB | Output is correct |

6 | Correct | 0 ms | 1364 KB | Output is correct |

7 | Correct | 2 ms | 1364 KB | Output is correct |

8 | Correct | 0 ms | 1364 KB | Output is correct |

9 | Correct | 2 ms | 1364 KB | Output is correct |

10 | Correct | 0 ms | 1364 KB | Output is correct |

11 | Correct | 2 ms | 1364 KB | Output is correct |

12 | Correct | 2 ms | 1364 KB | Output is correct |

13 | Correct | 0 ms | 1364 KB | Output is correct |

14 | Correct | 2 ms | 1364 KB | Output is correct |

15 | Correct | 0 ms | 1364 KB | Output is correct |

16 | Correct | 3 ms | 1364 KB | Output is correct |

17 | Correct | 3 ms | 1364 KB | Output is correct |

18 | Correct | 0 ms | 1364 KB | Output is correct |

19 | Correct | 3 ms | 1364 KB | Output is correct |

20 | Correct | 0 ms | 1364 KB | Output is correct |

21 | Correct | 0 ms | 1364 KB | Output is correct |

22 | Correct | 3 ms | 1364 KB | Output is correct |

23 | Correct | 3 ms | 1364 KB | Output is correct |

24 | Correct | 3 ms | 1364 KB | Output is correct |

25 | Correct | 0 ms | 1364 KB | Output is correct |

26 | Correct | 4 ms | 1364 KB | Output is correct |

27 | Correct | 4 ms | 1364 KB | Output is correct |

28 | Correct | 4 ms | 1364 KB | Output is correct |

29 | Correct | 4 ms | 1364 KB | Output is correct |

30 | Correct | 4 ms | 1364 KB | Output is correct |

31 | Correct | 4 ms | 1364 KB | Output is correct |

32 | Correct | 4 ms | 1364 KB | Output is correct |

33 | Correct | 2 ms | 1364 KB | Output is correct |

34 | Correct | 4 ms | 1364 KB | Output is correct |

35 | Correct | 4 ms | 1364 KB | Output is correct |

36 | Correct | 4 ms | 1364 KB | Output is correct |

37 | Correct | 5 ms | 1364 KB | Output is correct |

38 | Correct | 5 ms | 1364 KB | Output is correct |

39 | Correct | 5 ms | 1364 KB | Output is correct |

40 | Correct | 5 ms | 1364 KB | Output is correct |

41 | Correct | 5 ms | 1364 KB | Output is correct |

42 | Correct | 5 ms | 1364 KB | Output is correct |

43 | Correct | 5 ms | 1364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 236 ms | 1364 KB | Output is correct |

2 | Correct | 236 ms | 1364 KB | Output is correct |

3 | Correct | 406 ms | 1364 KB | Output is correct |

4 | Correct | 219 ms | 1364 KB | Output is correct |

5 | Correct | 341 ms | 1364 KB | Output is correct |

6 | Correct | 269 ms | 1364 KB | Output is correct |

7 | Correct | 204 ms | 1364 KB | Output is correct |

8 | Correct | 211 ms | 1364 KB | Output is correct |

9 | Correct | 225 ms | 1364 KB | Output is correct |

10 | Correct | 221 ms | 1364 KB | Output is correct |

11 | Correct | 382 ms | 1364 KB | Output is correct |

12 | Correct | 210 ms | 1364 KB | Output is correct |

13 | Correct | 326 ms | 1364 KB | Output is correct |

14 | Correct | 258 ms | 1364 KB | Output is correct |

15 | Correct | 196 ms | 1364 KB | Output is correct |

16 | Correct | 202 ms | 1364 KB | Output is correct |

17 | Correct | 205 ms | 1364 KB | Output is correct |

18 | Correct | 204 ms | 1364 KB | Output is correct |

19 | Correct | 339 ms | 1364 KB | Output is correct |

20 | Correct | 191 ms | 1364 KB | Output is correct |

21 | Correct | 295 ms | 1364 KB | Output is correct |

22 | Correct | 234 ms | 1364 KB | Output is correct |

23 | Correct | 180 ms | 1364 KB | Output is correct |

24 | Correct | 184 ms | 1364 KB | Output is correct |

25 | Correct | 173 ms | 1364 KB | Output is correct |

26 | Correct | 172 ms | 1364 KB | Output is correct |

27 | Correct | 281 ms | 1364 KB | Output is correct |

28 | Correct | 162 ms | 1364 KB | Output is correct |

29 | Correct | 256 ms | 1364 KB | Output is correct |

30 | Correct | 200 ms | 1364 KB | Output is correct |

31 | Correct | 152 ms | 1364 KB | Output is correct |

32 | Correct | 159 ms | 1364 KB | Output is correct |

33 | Correct | 135 ms | 1364 KB | Output is correct |

34 | Correct | 135 ms | 1364 KB | Output is correct |

35 | Correct | 201 ms | 1364 KB | Output is correct |

36 | Correct | 128 ms | 1364 KB | Output is correct |

37 | Correct | 196 ms | 1364 KB | Output is correct |

38 | Correct | 156 ms | 1364 KB | Output is correct |

39 | Correct | 118 ms | 1364 KB | Output is correct |

40 | Correct | 123 ms | 1364 KB | Output is correct |

41 | Correct | 264 ms | 1364 KB | Output is correct |

42 | Correct | 261 ms | 1364 KB | Output is correct |

43 | Correct | 270 ms | 1364 KB | Output is correct |

44 | Correct | 261 ms | 1364 KB | Output is correct |

45 | Correct | 269 ms | 1364 KB | Output is correct |

46 | Correct | 263 ms | 1364 KB | Output is correct |

47 | Correct | 273 ms | 1364 KB | Output is correct |

48 | Correct | 269 ms | 1364 KB | Output is correct |

49 | Correct | 271 ms | 1364 KB | Output is correct |

50 | Correct | 268 ms | 1364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 247 ms | 1364 KB | Output is correct |

2 | Correct | 235 ms | 1364 KB | Output is correct |

3 | Correct | 206 ms | 1364 KB | Output is correct |

4 | Correct | 179 ms | 1364 KB | Output is correct |

5 | Correct | 136 ms | 1364 KB | Output is correct |

6 | Correct | 138 ms | 1364 KB | Output is correct |

7 | Correct | 137 ms | 1364 KB | Output is correct |

8 | Correct | 135 ms | 1364 KB | Output is correct |

9 | Correct | 136 ms | 1364 KB | Output is correct |

10 | Correct | 137 ms | 1364 KB | Output is correct |

11 | Correct | 137 ms | 1364 KB | Output is correct |

12 | Correct | 77 ms | 1364 KB | Output is correct |

13 | Correct | 82 ms | 1364 KB | Output is correct |

14 | Correct | 82 ms | 1364 KB | Output is correct |

15 | Correct | 80 ms | 1364 KB | Output is correct |

16 | Correct | 79 ms | 1364 KB | Output is correct |

17 | Correct | 83 ms | 1364 KB | Output is correct |

18 | Correct | 81 ms | 1364 KB | Output is correct |

19 | Correct | 20 ms | 1364 KB | Output is correct |

20 | Correct | 19 ms | 1364 KB | Output is correct |

21 | Correct | 19 ms | 1364 KB | Output is correct |

22 | Correct | 18 ms | 1364 KB | Output is correct |

23 | Correct | 19 ms | 1364 KB | Output is correct |

24 | Correct | 17 ms | 1364 KB | Output is correct |

25 | Correct | 19 ms | 1364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 242 ms | 1364 KB | Output is correct |

2 | Correct | 244 ms | 1364 KB | Output is correct |

3 | Correct | 245 ms | 1364 KB | Output is correct |

4 | Correct | 236 ms | 1364 KB | Output is correct |

5 | Correct | 190 ms | 1364 KB | Output is correct |

6 | Correct | 191 ms | 1364 KB | Output is correct |

7 | Correct | 187 ms | 1364 KB | Output is correct |

8 | Correct | 188 ms | 1364 KB | Output is correct |

9 | Correct | 190 ms | 1364 KB | Output is correct |

10 | Correct | 239 ms | 1364 KB | Output is correct |

11 | Correct | 233 ms | 1364 KB | Output is correct |

12 | Correct | 235 ms | 1364 KB | Output is correct |

13 | Correct | 234 ms | 1364 KB | Output is correct |

14 | Correct | 229 ms | 1364 KB | Output is correct |

15 | Correct | 182 ms | 1364 KB | Output is correct |

16 | Correct | 178 ms | 1364 KB | Output is correct |

17 | Correct | 182 ms | 1364 KB | Output is correct |

18 | Correct | 180 ms | 1364 KB | Output is correct |

19 | Correct | 181 ms | 1364 KB | Output is correct |

20 | Correct | 230 ms | 1364 KB | Output is correct |

21 | Correct | 214 ms | 1364 KB | Output is correct |

22 | Correct | 215 ms | 1364 KB | Output is correct |

23 | Correct | 211 ms | 1364 KB | Output is correct |

24 | Correct | 207 ms | 1364 KB | Output is correct |

25 | Correct | 162 ms | 1364 KB | Output is correct |

26 | Correct | 167 ms | 1364 KB | Output is correct |

27 | Correct | 165 ms | 1364 KB | Output is correct |

28 | Correct | 164 ms | 1364 KB | Output is correct |

29 | Correct | 168 ms | 1364 KB | Output is correct |

30 | Correct | 212 ms | 1364 KB | Output is correct |

31 | Correct | 185 ms | 1364 KB | Output is correct |

32 | Correct | 184 ms | 1364 KB | Output is correct |

33 | Correct | 182 ms | 1364 KB | Output is correct |

34 | Correct | 178 ms | 1364 KB | Output is correct |

35 | Correct | 143 ms | 1364 KB | Output is correct |

36 | Correct | 145 ms | 1364 KB | Output is correct |

37 | Correct | 142 ms | 1364 KB | Output is correct |

38 | Correct | 141 ms | 1364 KB | Output is correct |

39 | Correct | 141 ms | 1364 KB | Output is correct |

40 | Correct | 184 ms | 1364 KB | Output is correct |