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

1095322 | 2024-10-01T21:03:11 Z | alexander707070 | Triangles (CEOI18_tri) | C++14 | 32 ms | 2652 KB |

#include <bits/stdc++.h> #include "trilib.h" #define MAXN 200007 using namespace std; int n; /*static long long *x, *y; static int queries=0; static void init() { static int is_inited=0; if (is_inited) return; is_inited=1; assert(scanf("%d", &n)==1); x=(long long*)malloc((n+1)*sizeof(long long)); y=(long long*)malloc((n+1)*sizeof(long long)); for (int i=1; i<=n; i++){ //x[i]=rand()%100+1; //y[i]=rand()%100+1; cin>>x[i]>>y[i]; //assert(scanf("%lld%lld", &x[i], &y[i])==2); } } int get_n() { init(); return n; } int is_clockwise(int a, int b, int c) { init(); assert(a>=1 && a<=n); assert(b>=1 && b<=n); assert(c>=1 && c<=n); assert(a!=b && a!=c && b!=c); queries++; if(queries == 1000 * 1000 + 1) printf("Too many queries!"); return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0; } void give_answer(int s) { init(); printf("%d\n", s); }*/ bool cmp(int x,int y){ return is_clockwise(1,x,y); } vector<int> l,r,res; int s[MAXN],ss[MAXN],cnt[MAXN],sol; void shift(int x){ for(int i=1;i<=n;i++){ if(i+x<=n)ss[i+x]=s[i]; else ss[i+x-n]=s[i]; } for(int i=1;i<=n;i++)s[i]=ss[i]; } int main(){ srand(42069); n=get_n(); for(int i=2;i<=n-1;i++){ if(!is_clockwise(1,n,i)){ l.push_back(i); }else{ r.push_back(i); } } sort(l.begin(),l.end(),cmp); sort(r.begin(),r.end(),cmp); s[1]=1; for(int i=0;i<l.size();i++){ s[i+2]=l[i]; } s[l.size()+2]=n; for(int i=0;i<r.size();i++){ s[l.size()+3+i]=r[i]; } for(int test=1;test<=20;test++){ res.clear(); shift(rand()%n); for(int i=1;i<=n;i++){ while(res.size()>=2 and !is_clockwise(res[res.size()-2],res[res.size()-1],s[i])){ res.pop_back(); } res.push_back(s[i]); } for(int i:res)cnt[i]++; } for(int i=1;i<=n;i++){ if(cnt[i]==20)sol++; } give_answer(sol); return 0; }

### Compilation message

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

1 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

7 | Correct | 0 ms | 348 KB | Output is correct |

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

9 | Correct | 0 ms | 348 KB | Output is correct |

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

11 | Correct | 0 ms | 348 KB | Output is correct |

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

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

14 | Correct | 1 ms | 348 KB | Output is correct |

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

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

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

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

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

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

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

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

23 | Correct | 1 ms | 348 KB | Output is correct |

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

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

26 | Correct | 0 ms | 348 KB | Output is correct |

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

1 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

7 | Correct | 0 ms | 348 KB | Output is correct |

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

9 | Correct | 0 ms | 348 KB | Output is correct |

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

11 | Correct | 0 ms | 348 KB | Output is correct |

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

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

14 | Correct | 1 ms | 348 KB | Output is correct |

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

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

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

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

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

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

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

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

23 | Correct | 1 ms | 348 KB | Output is correct |

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

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

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 0 ms | 344 KB | Output is correct |

28 | Correct | 0 ms | 348 KB | Output is correct |

29 | Correct | 0 ms | 348 KB | Output is correct |

30 | Correct | 0 ms | 448 KB | Output is correct |

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

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

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

34 | Correct | 1 ms | 348 KB | Output is correct |

35 | Correct | 1 ms | 348 KB | Output is correct |

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

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

38 | Correct | 1 ms | 348 KB | Output is correct |

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

40 | Correct | 0 ms | 348 KB | Output is correct |

41 | Correct | 1 ms | 348 KB | Output is correct |

42 | Correct | 1 ms | 348 KB | Output is correct |

43 | Correct | 0 ms | 348 KB | Output is correct |

44 | Correct | 0 ms | 348 KB | Output is correct |

45 | Correct | 0 ms | 348 KB | Output is correct |

46 | Correct | 1 ms | 348 KB | Output is correct |

47 | Correct | 0 ms | 348 KB | Output is correct |

48 | Correct | 1 ms | 348 KB | Output is correct |

49 | Correct | 0 ms | 348 KB | Output is correct |

50 | Correct | 0 ms | 452 KB | Output is correct |

51 | Correct | 1 ms | 348 KB | Output is correct |

52 | Correct | 1 ms | 348 KB | Output is correct |

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

1 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

7 | Correct | 0 ms | 348 KB | Output is correct |

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

9 | Correct | 0 ms | 348 KB | Output is correct |

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

11 | Correct | 0 ms | 348 KB | Output is correct |

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

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

14 | Correct | 1 ms | 348 KB | Output is correct |

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

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

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

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

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

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

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

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

23 | Correct | 1 ms | 348 KB | Output is correct |

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

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

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 0 ms | 344 KB | Output is correct |

28 | Correct | 0 ms | 348 KB | Output is correct |

29 | Correct | 0 ms | 348 KB | Output is correct |

30 | Correct | 0 ms | 448 KB | Output is correct |

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

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

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

34 | Correct | 1 ms | 348 KB | Output is correct |

35 | Correct | 1 ms | 348 KB | Output is correct |

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

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

38 | Correct | 1 ms | 348 KB | Output is correct |

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

40 | Correct | 0 ms | 348 KB | Output is correct |

41 | Correct | 1 ms | 348 KB | Output is correct |

42 | Correct | 1 ms | 348 KB | Output is correct |

43 | Correct | 0 ms | 348 KB | Output is correct |

44 | Correct | 0 ms | 348 KB | Output is correct |

45 | Correct | 0 ms | 348 KB | Output is correct |

46 | Correct | 1 ms | 348 KB | Output is correct |

47 | Correct | 0 ms | 348 KB | Output is correct |

48 | Correct | 1 ms | 348 KB | Output is correct |

49 | Correct | 0 ms | 348 KB | Output is correct |

50 | Correct | 0 ms | 452 KB | Output is correct |

51 | Correct | 1 ms | 348 KB | Output is correct |

52 | Correct | 1 ms | 348 KB | Output is correct |

53 | Correct | 0 ms | 448 KB | Output is correct |

54 | Correct | 0 ms | 344 KB | Output is correct |

55 | Correct | 0 ms | 348 KB | Output is correct |

56 | Correct | 0 ms | 348 KB | Output is correct |

57 | Correct | 0 ms | 348 KB | Output is correct |

58 | Correct | 11 ms | 1104 KB | Output is correct |

59 | Correct | 11 ms | 1116 KB | Output is correct |

60 | Correct | 11 ms | 1136 KB | Output is correct |

61 | Correct | 11 ms | 1300 KB | Output is correct |

62 | Correct | 7 ms | 1372 KB | Output is correct |

63 | Correct | 7 ms | 1116 KB | Output is correct |

64 | Correct | 8 ms | 1372 KB | Output is correct |

65 | Correct | 8 ms | 1372 KB | Output is correct |

66 | Correct | 15 ms | 1272 KB | Output is correct |

67 | Correct | 11 ms | 1116 KB | Output is correct |

68 | Correct | 12 ms | 1088 KB | Output is correct |

69 | Correct | 11 ms | 1116 KB | Output is correct |

70 | Correct | 10 ms | 1224 KB | Output is correct |

71 | Correct | 11 ms | 1112 KB | Output is correct |

72 | Correct | 11 ms | 1100 KB | Output is correct |

73 | Correct | 11 ms | 1116 KB | Output is correct |

74 | Correct | 10 ms | 1264 KB | Output is correct |

75 | Correct | 10 ms | 1116 KB | Output is correct |

76 | Correct | 11 ms | 1276 KB | Output is correct |

77 | Correct | 6 ms | 1116 KB | Output is correct |

78 | Correct | 6 ms | 1116 KB | Output is correct |

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

1 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

7 | Correct | 0 ms | 348 KB | Output is correct |

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

9 | Correct | 0 ms | 348 KB | Output is correct |

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

11 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

23 | Correct | 0 ms | 348 KB | Output is correct |

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

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

26 | Correct | 0 ms | 344 KB | Output is correct |

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

1 | Correct | 0 ms | 348 KB | Output is correct |

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

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

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

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

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

7 | Correct | 0 ms | 348 KB | Output is correct |

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

9 | Correct | 0 ms | 348 KB | Output is correct |

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

11 | Correct | 0 ms | 348 KB | Output is correct |

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

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

14 | Correct | 1 ms | 348 KB | Output is correct |

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

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

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

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

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

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

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

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

23 | Correct | 1 ms | 348 KB | Output is correct |

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

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

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 0 ms | 344 KB | Output is correct |

28 | Correct | 0 ms | 348 KB | Output is correct |

29 | Correct | 0 ms | 348 KB | Output is correct |

30 | Correct | 0 ms | 448 KB | Output is correct |

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

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

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

34 | Correct | 1 ms | 348 KB | Output is correct |

35 | Correct | 1 ms | 348 KB | Output is correct |

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

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

38 | Correct | 1 ms | 348 KB | Output is correct |

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

40 | Correct | 0 ms | 348 KB | Output is correct |

41 | Correct | 1 ms | 348 KB | Output is correct |

42 | Correct | 1 ms | 348 KB | Output is correct |

43 | Correct | 0 ms | 348 KB | Output is correct |

44 | Correct | 0 ms | 348 KB | Output is correct |

45 | Correct | 0 ms | 348 KB | Output is correct |

46 | Correct | 1 ms | 348 KB | Output is correct |

47 | Correct | 0 ms | 348 KB | Output is correct |

48 | Correct | 1 ms | 348 KB | Output is correct |

49 | Correct | 0 ms | 348 KB | Output is correct |

50 | Correct | 0 ms | 452 KB | Output is correct |

51 | Correct | 1 ms | 348 KB | Output is correct |

52 | Correct | 1 ms | 348 KB | Output is correct |

53 | Correct | 0 ms | 448 KB | Output is correct |

54 | Correct | 0 ms | 344 KB | Output is correct |

55 | Correct | 0 ms | 348 KB | Output is correct |

56 | Correct | 0 ms | 348 KB | Output is correct |

57 | Correct | 0 ms | 348 KB | Output is correct |

58 | Correct | 11 ms | 1104 KB | Output is correct |

59 | Correct | 11 ms | 1116 KB | Output is correct |

60 | Correct | 11 ms | 1136 KB | Output is correct |

61 | Correct | 11 ms | 1300 KB | Output is correct |

62 | Correct | 7 ms | 1372 KB | Output is correct |

63 | Correct | 7 ms | 1116 KB | Output is correct |

64 | Correct | 8 ms | 1372 KB | Output is correct |

65 | Correct | 8 ms | 1372 KB | Output is correct |

66 | Correct | 15 ms | 1272 KB | Output is correct |

67 | Correct | 11 ms | 1116 KB | Output is correct |

68 | Correct | 12 ms | 1088 KB | Output is correct |

69 | Correct | 11 ms | 1116 KB | Output is correct |

70 | Correct | 10 ms | 1224 KB | Output is correct |

71 | Correct | 11 ms | 1112 KB | Output is correct |

72 | Correct | 11 ms | 1100 KB | Output is correct |

73 | Correct | 11 ms | 1116 KB | Output is correct |

74 | Correct | 10 ms | 1264 KB | Output is correct |

75 | Correct | 10 ms | 1116 KB | Output is correct |

76 | Correct | 11 ms | 1276 KB | Output is correct |

77 | Correct | 6 ms | 1116 KB | Output is correct |

78 | Correct | 6 ms | 1116 KB | Output is correct |

79 | Correct | 0 ms | 348 KB | Output is correct |

80 | Correct | 0 ms | 348 KB | Output is correct |

81 | Correct | 0 ms | 348 KB | Output is correct |

82 | Correct | 0 ms | 348 KB | Output is correct |

83 | Correct | 0 ms | 444 KB | Output is correct |

84 | Correct | 0 ms | 348 KB | Output is correct |

85 | Correct | 0 ms | 348 KB | Output is correct |

86 | Correct | 0 ms | 604 KB | Output is correct |

87 | Correct | 0 ms | 348 KB | Output is correct |

88 | Correct | 0 ms | 348 KB | Output is correct |

89 | Correct | 0 ms | 348 KB | Output is correct |

90 | Correct | 0 ms | 348 KB | Output is correct |

91 | Correct | 0 ms | 348 KB | Output is correct |

92 | Correct | 0 ms | 348 KB | Output is correct |

93 | Correct | 0 ms | 348 KB | Output is correct |

94 | Correct | 0 ms | 348 KB | Output is correct |

95 | Correct | 0 ms | 344 KB | Output is correct |

96 | Correct | 1 ms | 348 KB | Output is correct |

97 | Correct | 0 ms | 348 KB | Output is correct |

98 | Correct | 0 ms | 448 KB | Output is correct |

99 | Correct | 0 ms | 348 KB | Output is correct |

100 | Correct | 0 ms | 348 KB | Output is correct |

101 | Correct | 0 ms | 348 KB | Output is correct |

102 | Correct | 0 ms | 440 KB | Output is correct |

103 | Correct | 0 ms | 348 KB | Output is correct |

104 | Correct | 0 ms | 344 KB | Output is correct |

105 | Correct | 1 ms | 348 KB | Output is correct |

106 | Correct | 0 ms | 348 KB | Output is correct |

107 | Correct | 0 ms | 344 KB | Output is correct |

108 | Correct | 0 ms | 348 KB | Output is correct |

109 | Correct | 1 ms | 348 KB | Output is correct |

110 | Incorrect | 32 ms | 2652 KB | Output isn't correct |

111 | Halted | 0 ms | 0 KB | - |