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

473109 | 2021-09-15T07:38:42 Z | blue | Arranging Shoes (IOI19_shoes) | C++17 | 119 ms | 17332 KB |

#include "shoes.h" #include <vector> #include <iostream> #include <algorithm> using namespace std; const int maxN = 100'000; vector<int> A[1+maxN]; vector<int> B[1+maxN]; vector<int> actpos; long long count_swaps(vector<int> S) { int N = (int)S.size()/2; for(int i = 0; i < 2*N; i++) { if(S[i] < 0) A[ -S[i] ].push_back(i); else B[ S[i] ].push_back(i); } long long res = 0; vector< pair<int, int> > X; for(int s = 1; s <= N; s++) { for(int i = 0; i < A[s].size(); i++) { if(A[s][i] > B[s][i]) { swap(A[s][i], B[s][i]); res++; } X.push_back(make_pair(A[s][i], B[s][i])); } } sort(X.begin(), X.end()); actpos = vector<int>(2*N); int ct = -1; for(pair<int, int> x: X) { actpos[ x.first ] = ++ct; actpos[ x.second ] = ++ct; } vector<int> a_sort(2*N); for(int i = 0; i < 2*N; i++) a_sort[i] = i; sort(a_sort.begin(), a_sort.end(), [] (int u, int v) { return actpos[u] > actpos[v]; }); vector<int> BIT(1+2*N, 0); for(int g: a_sort) { for(int i = g+1 - 1; i >= 1; i -= i&-i) res += BIT[i]; for(int i = g+1; i <= 2*N; i += i&-i) BIT[i]++; } return res; }

### Compilation message

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

3 | Correct | 3 ms | 4940 KB | Output is correct |

4 | Correct | 3 ms | 4940 KB | Output is correct |

5 | Correct | 3 ms | 4940 KB | Output is correct |

6 | Correct | 3 ms | 4940 KB | Output is correct |

7 | Correct | 3 ms | 4988 KB | Output is correct |

8 | Correct | 3 ms | 4940 KB | Output is correct |

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

10 | Correct | 3 ms | 4992 KB | Output is correct |

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

12 | Correct | 3 ms | 4940 KB | Output is correct |

13 | Correct | 4 ms | 5056 KB | Output is correct |

14 | Correct | 3 ms | 4940 KB | Output is correct |

15 | Correct | 4 ms | 4940 KB | Output is correct |

16 | Correct | 4 ms | 4940 KB | Output is correct |

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

18 | Correct | 3 ms | 4940 KB | Output is correct |

19 | Correct | 4 ms | 4988 KB | Output is correct |

20 | Correct | 4 ms | 4940 KB | Output is correct |

21 | Correct | 3 ms | 4940 KB | Output is correct |

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

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

24 | Correct | 4 ms | 4940 KB | Output is correct |

25 | Correct | 4 ms | 4940 KB | Output is correct |

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

27 | Correct | 3 ms | 4940 KB | Output is correct |

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

29 | Correct | 3 ms | 4940 KB | Output is correct |

30 | Correct | 3 ms | 4940 KB | Output is correct |

31 | Correct | 3 ms | 4940 KB | Output is correct |

32 | Correct | 3 ms | 4940 KB | Output is correct |

33 | Correct | 3 ms | 4940 KB | Output is correct |

34 | Correct | 3 ms | 4940 KB | Output is correct |

35 | Correct | 3 ms | 4940 KB | Output is correct |

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

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

3 | Correct | 3 ms | 4940 KB | Output is correct |

4 | Correct | 3 ms | 4940 KB | Output is correct |

5 | Correct | 3 ms | 4992 KB | Output is correct |

6 | Correct | 3 ms | 4940 KB | Output is correct |

7 | Correct | 4 ms | 4940 KB | Output is correct |

8 | Correct | 3 ms | 4940 KB | Output is correct |

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

10 | Correct | 3 ms | 4940 KB | Output is correct |

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

12 | Correct | 3 ms | 4940 KB | Output is correct |

13 | Correct | 3 ms | 4940 KB | Output is correct |

14 | Correct | 3 ms | 5068 KB | Output is correct |

15 | Correct | 4 ms | 4940 KB | Output is correct |

16 | Correct | 4 ms | 4940 KB | Output is correct |

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

18 | Correct | 4 ms | 4996 KB | Output is correct |

19 | Correct | 4 ms | 4940 KB | Output is correct |

20 | Correct | 8 ms | 5644 KB | Output is correct |

21 | Correct | 8 ms | 5580 KB | Output is correct |

22 | Correct | 55 ms | 10720 KB | Output is correct |

23 | Correct | 51 ms | 10612 KB | Output is correct |

24 | Correct | 55 ms | 10712 KB | Output is correct |

25 | Correct | 71 ms | 10728 KB | Output is correct |

26 | Correct | 65 ms | 10804 KB | Output is correct |

27 | Correct | 47 ms | 10704 KB | Output is correct |

28 | Correct | 73 ms | 10680 KB | Output is correct |

29 | Correct | 72 ms | 10724 KB | Output is correct |

30 | Correct | 71 ms | 10724 KB | Output is correct |

31 | Correct | 54 ms | 10644 KB | Output is correct |

32 | Correct | 86 ms | 10716 KB | Output is correct |

33 | Correct | 71 ms | 10680 KB | Output is correct |

34 | Correct | 73 ms | 10624 KB | Output is correct |

35 | Correct | 3 ms | 4940 KB | Output is correct |

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

37 | Correct | 71 ms | 10628 KB | Output is correct |

38 | Correct | 82 ms | 10616 KB | Output is correct |

39 | Correct | 72 ms | 10616 KB | Output is correct |

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

3 | Correct | 4 ms | 4948 KB | Output is correct |

4 | Correct | 4 ms | 4940 KB | Output is correct |

5 | Correct | 111 ms | 16276 KB | Output is correct |

6 | Correct | 97 ms | 11472 KB | Output is correct |

7 | Correct | 100 ms | 16292 KB | Output is correct |

8 | Correct | 78 ms | 10888 KB | Output is correct |

9 | Correct | 102 ms | 16284 KB | Output is correct |

10 | Correct | 96 ms | 13268 KB | Output is correct |

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

3 | Correct | 3 ms | 4940 KB | Output is correct |

4 | Correct | 3 ms | 4940 KB | Output is correct |

5 | Correct | 3 ms | 4940 KB | Output is correct |

6 | Correct | 3 ms | 4940 KB | Output is correct |

7 | Correct | 3 ms | 4988 KB | Output is correct |

8 | Correct | 3 ms | 4940 KB | Output is correct |

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

10 | Correct | 3 ms | 4992 KB | Output is correct |

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

12 | Correct | 3 ms | 4940 KB | Output is correct |

13 | Correct | 4 ms | 5056 KB | Output is correct |

14 | Correct | 3 ms | 4940 KB | Output is correct |

15 | Correct | 4 ms | 4940 KB | Output is correct |

16 | Correct | 4 ms | 4940 KB | Output is correct |

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

18 | Correct | 3 ms | 4940 KB | Output is correct |

19 | Correct | 4 ms | 4988 KB | Output is correct |

20 | Correct | 4 ms | 4940 KB | Output is correct |

21 | Correct | 3 ms | 4940 KB | Output is correct |

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

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

24 | Correct | 4 ms | 4940 KB | Output is correct |

25 | Correct | 4 ms | 4940 KB | Output is correct |

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

27 | Correct | 3 ms | 4940 KB | Output is correct |

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

29 | Correct | 3 ms | 4940 KB | Output is correct |

30 | Correct | 3 ms | 4940 KB | Output is correct |

31 | Correct | 3 ms | 4940 KB | Output is correct |

32 | Correct | 3 ms | 4940 KB | Output is correct |

33 | Correct | 3 ms | 4940 KB | Output is correct |

34 | Correct | 3 ms | 4940 KB | Output is correct |

35 | Correct | 3 ms | 4940 KB | Output is correct |

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

37 | Correct | 3 ms | 4940 KB | Output is correct |

38 | Correct | 3 ms | 4940 KB | Output is correct |

39 | Correct | 4 ms | 4940 KB | Output is correct |

40 | Correct | 4 ms | 4940 KB | Output is correct |

41 | Correct | 4 ms | 5068 KB | Output is correct |

42 | Correct | 4 ms | 5068 KB | Output is correct |

43 | Correct | 4 ms | 5068 KB | Output is correct |

44 | Correct | 5 ms | 5068 KB | Output is correct |

45 | Correct | 4 ms | 5068 KB | Output is correct |

46 | Correct | 4 ms | 5068 KB | Output is correct |

47 | Correct | 4 ms | 5068 KB | Output is correct |

48 | Correct | 4 ms | 5068 KB | Output is correct |

49 | Correct | 4 ms | 5000 KB | Output is correct |

50 | Correct | 4 ms | 5068 KB | Output is correct |

51 | Correct | 4 ms | 5040 KB | Output is correct |

52 | Correct | 4 ms | 5068 KB | Output is correct |

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

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

2 | Correct | 3 ms | 4940 KB | Output is correct |

3 | Correct | 3 ms | 4940 KB | Output is correct |

4 | Correct | 3 ms | 4940 KB | Output is correct |

5 | Correct | 3 ms | 4940 KB | Output is correct |

6 | Correct | 3 ms | 4940 KB | Output is correct |

7 | Correct | 3 ms | 4988 KB | Output is correct |

8 | Correct | 3 ms | 4940 KB | Output is correct |

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

10 | Correct | 3 ms | 4992 KB | Output is correct |

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

12 | Correct | 3 ms | 4940 KB | Output is correct |

13 | Correct | 4 ms | 5056 KB | Output is correct |

14 | Correct | 3 ms | 4940 KB | Output is correct |

15 | Correct | 4 ms | 4940 KB | Output is correct |

16 | Correct | 4 ms | 4940 KB | Output is correct |

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

18 | Correct | 3 ms | 4940 KB | Output is correct |

19 | Correct | 4 ms | 4988 KB | Output is correct |

20 | Correct | 4 ms | 4940 KB | Output is correct |

21 | Correct | 3 ms | 4940 KB | Output is correct |

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

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

24 | Correct | 4 ms | 4940 KB | Output is correct |

25 | Correct | 4 ms | 4940 KB | Output is correct |

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

27 | Correct | 3 ms | 4940 KB | Output is correct |

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

29 | Correct | 3 ms | 4940 KB | Output is correct |

30 | Correct | 3 ms | 4940 KB | Output is correct |

31 | Correct | 3 ms | 4940 KB | Output is correct |

32 | Correct | 3 ms | 4940 KB | Output is correct |

33 | Correct | 3 ms | 4940 KB | Output is correct |

34 | Correct | 3 ms | 4940 KB | Output is correct |

35 | Correct | 3 ms | 4940 KB | Output is correct |

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

37 | Correct | 3 ms | 4940 KB | Output is correct |

38 | Correct | 3 ms | 4940 KB | Output is correct |

39 | Correct | 3 ms | 4992 KB | Output is correct |

40 | Correct | 3 ms | 4940 KB | Output is correct |

41 | Correct | 4 ms | 4940 KB | Output is correct |

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

43 | Correct | 3 ms | 4940 KB | Output is correct |

44 | Correct | 3 ms | 4940 KB | Output is correct |

45 | Correct | 3 ms | 4940 KB | Output is correct |

46 | Correct | 3 ms | 4940 KB | Output is correct |

47 | Correct | 3 ms | 4940 KB | Output is correct |

48 | Correct | 3 ms | 5068 KB | Output is correct |

49 | Correct | 4 ms | 4940 KB | Output is correct |

50 | Correct | 4 ms | 4940 KB | Output is correct |

51 | Correct | 3 ms | 4988 KB | Output is correct |

52 | Correct | 4 ms | 4996 KB | Output is correct |

53 | Correct | 4 ms | 4940 KB | Output is correct |

54 | Correct | 8 ms | 5644 KB | Output is correct |

55 | Correct | 8 ms | 5580 KB | Output is correct |

56 | Correct | 55 ms | 10720 KB | Output is correct |

57 | Correct | 51 ms | 10612 KB | Output is correct |

58 | Correct | 55 ms | 10712 KB | Output is correct |

59 | Correct | 71 ms | 10728 KB | Output is correct |

60 | Correct | 65 ms | 10804 KB | Output is correct |

61 | Correct | 47 ms | 10704 KB | Output is correct |

62 | Correct | 73 ms | 10680 KB | Output is correct |

63 | Correct | 72 ms | 10724 KB | Output is correct |

64 | Correct | 71 ms | 10724 KB | Output is correct |

65 | Correct | 54 ms | 10644 KB | Output is correct |

66 | Correct | 86 ms | 10716 KB | Output is correct |

67 | Correct | 71 ms | 10680 KB | Output is correct |

68 | Correct | 73 ms | 10624 KB | Output is correct |

69 | Correct | 3 ms | 4940 KB | Output is correct |

70 | Correct | 4 ms | 4920 KB | Output is correct |

71 | Correct | 71 ms | 10628 KB | Output is correct |

72 | Correct | 82 ms | 10616 KB | Output is correct |

73 | Correct | 72 ms | 10616 KB | Output is correct |

74 | Correct | 4 ms | 4940 KB | Output is correct |

75 | Correct | 3 ms | 4940 KB | Output is correct |

76 | Correct | 4 ms | 4948 KB | Output is correct |

77 | Correct | 4 ms | 4940 KB | Output is correct |

78 | Correct | 111 ms | 16276 KB | Output is correct |

79 | Correct | 97 ms | 11472 KB | Output is correct |

80 | Correct | 100 ms | 16292 KB | Output is correct |

81 | Correct | 78 ms | 10888 KB | Output is correct |

82 | Correct | 102 ms | 16284 KB | Output is correct |

83 | Correct | 96 ms | 13268 KB | Output is correct |

84 | Correct | 3 ms | 4940 KB | Output is correct |

85 | Correct | 3 ms | 4940 KB | Output is correct |

86 | Correct | 4 ms | 4940 KB | Output is correct |

87 | Correct | 4 ms | 4940 KB | Output is correct |

88 | Correct | 4 ms | 5068 KB | Output is correct |

89 | Correct | 4 ms | 5068 KB | Output is correct |

90 | Correct | 4 ms | 5068 KB | Output is correct |

91 | Correct | 5 ms | 5068 KB | Output is correct |

92 | Correct | 4 ms | 5068 KB | Output is correct |

93 | Correct | 4 ms | 5068 KB | Output is correct |

94 | Correct | 4 ms | 5068 KB | Output is correct |

95 | Correct | 4 ms | 5068 KB | Output is correct |

96 | Correct | 4 ms | 5000 KB | Output is correct |

97 | Correct | 4 ms | 5068 KB | Output is correct |

98 | Correct | 4 ms | 5040 KB | Output is correct |

99 | Correct | 4 ms | 5068 KB | Output is correct |

100 | Correct | 4 ms | 5068 KB | Output is correct |

101 | Correct | 11 ms | 6060 KB | Output is correct |

102 | Correct | 10 ms | 5708 KB | Output is correct |

103 | Correct | 99 ms | 17256 KB | Output is correct |

104 | Correct | 88 ms | 17332 KB | Output is correct |

105 | Correct | 102 ms | 14588 KB | Output is correct |

106 | Correct | 119 ms | 17208 KB | Output is correct |

107 | Correct | 78 ms | 12668 KB | Output is correct |

108 | Correct | 70 ms | 12924 KB | Output is correct |

109 | Correct | 85 ms | 12272 KB | Output is correct |

110 | Correct | 73 ms | 11864 KB | Output is correct |

111 | Correct | 105 ms | 16624 KB | Output is correct |

112 | Correct | 107 ms | 15864 KB | Output is correct |

113 | Correct | 80 ms | 12608 KB | Output is correct |

114 | Correct | 98 ms | 17208 KB | Output is correct |

115 | Correct | 109 ms | 17268 KB | Output is correct |