# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
984572 | 2024-05-16T19:17:17 Z | SzymonKrzywda | Arranging Shoes (IOI19_shoes) | C++17 | 64 ms | 20948 KB |
//#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int base = 2<<18; int tree[base*2+7]; void edit(int n){ n+=base; while (n>0){ tree[n] += 1; n/=2; } } int query(int a,int b){ a+=base-1; b+=base+1; int wynik=0; while (a/2 != b/2){ if (a%2==0) wynik += tree[a+1]; if (b%2==1) wynik += tree[b-1]; a/=2; b/=2; } return wynik; } long unsigned int count_swaps(vector<int>S){ long long wynik = 0,len=S.size(),idx_1=0,akt_liczba=0,idx_2=0,idx_3=0; pair< vector<int>,int> idx[200007]; int base_2 = 100001; for (int i=0; i<S.size(); i++){ idx[S[i]+base_2].first.push_back(i); } vector<pair<int,int>> stos(0); bool uzyte[200007]; //Zerujemy for (int i=0; i<200007; i++) uzyte[i] = false; for (int i=0; i<S.size(); i++){ //cout << i << " " << uzyte[i] << endl; if (!uzyte[i]){ idx_1 = i; idx_2 = idx[(-S[i])+base_2].first[idx[(-S[i])+base_2].second]; idx[(-S[i])+base_2].second += 1; idx[S[i]+base_2].second +=1; uzyte[idx_1] = true; uzyte[idx_2] = true; if (S[idx_2] < S[idx_1]) swap(idx_1,idx_2); stos.push_back({idx_1,idx_2}); } } //cout << stos.size() << endl; for (int i=0; i<stos.size(); i++){ //cout << stos[i].first << " " << stos[i].second << endl; idx_2=stos[i].first; wynik += idx_2-(i*2)+query(idx_2+1,len); edit(idx_2); //cout << wynik << endl; idx_3 = stos[i].second; wynik += idx_3-((i*2)+1)+query(idx_3+1,len); edit(idx_3); //cout << wynik << endl << endl; } for (int j=0; j<base*2+7; j++){ tree[j] = 0; } return wynik; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10844 KB | Output is correct |
2 | Correct | 5 ms | 10844 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10844 KB | Output is correct |
2 | Correct | 5 ms | 10844 KB | Output is correct |
3 | Correct | 6 ms | 10844 KB | Output is correct |
4 | Correct | 6 ms | 10872 KB | Output is correct |
5 | Correct | 5 ms | 10844 KB | Output is correct |
6 | Correct | 5 ms | 10844 KB | Output is correct |
7 | Correct | 6 ms | 10844 KB | Output is correct |
8 | Correct | 6 ms | 10844 KB | Output is correct |
9 | Correct | 6 ms | 10844 KB | Output is correct |
10 | Correct | 6 ms | 10844 KB | Output is correct |
11 | Correct | 5 ms | 10844 KB | Output is correct |
12 | Correct | 5 ms | 10840 KB | Output is correct |
13 | Correct | 8 ms | 10948 KB | Output is correct |
14 | Correct | 7 ms | 10844 KB | Output is correct |
15 | Correct | 6 ms | 10844 KB | Output is correct |
16 | Correct | 6 ms | 10844 KB | Output is correct |
17 | Correct | 5 ms | 10840 KB | Output is correct |
18 | Correct | 6 ms | 10840 KB | Output is correct |
19 | Correct | 6 ms | 10840 KB | Output is correct |
20 | Correct | 6 ms | 10844 KB | Output is correct |
21 | Correct | 6 ms | 10844 KB | Output is correct |
22 | Correct | 6 ms | 11096 KB | Output is correct |
23 | Correct | 5 ms | 10844 KB | Output is correct |
24 | Correct | 6 ms | 11096 KB | Output is correct |
25 | Correct | 6 ms | 10844 KB | Output is correct |
26 | Correct | 6 ms | 10844 KB | Output is correct |
27 | Correct | 6 ms | 10768 KB | Output is correct |
28 | Correct | 6 ms | 10844 KB | Output is correct |
29 | Correct | 7 ms | 10892 KB | Output is correct |
30 | Correct | 6 ms | 10844 KB | Output is correct |
31 | Correct | 6 ms | 10844 KB | Output is correct |
32 | Correct | 6 ms | 10844 KB | Output is correct |
33 | Correct | 6 ms | 10844 KB | Output is correct |
34 | Correct | 5 ms | 10844 KB | Output is correct |
35 | Correct | 6 ms | 10844 KB | Output is correct |
36 | Correct | 6 ms | 10844 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10844 KB | Output is correct |
2 | Correct | 5 ms | 10844 KB | Output is correct |
3 | Correct | 6 ms | 10844 KB | Output is correct |
4 | Correct | 6 ms | 10844 KB | Output is correct |
5 | Correct | 6 ms | 10840 KB | Output is correct |
6 | Correct | 6 ms | 10844 KB | Output is correct |
7 | Correct | 5 ms | 10844 KB | Output is correct |
8 | Correct | 6 ms | 10844 KB | Output is correct |
9 | Correct | 6 ms | 10844 KB | Output is correct |
10 | Correct | 6 ms | 10840 KB | Output is correct |
11 | Correct | 6 ms | 10844 KB | Output is correct |
12 | Correct | 6 ms | 10844 KB | Output is correct |
13 | Correct | 6 ms | 10844 KB | Output is correct |
14 | Correct | 6 ms | 10844 KB | Output is correct |
15 | Correct | 6 ms | 10844 KB | Output is correct |
16 | Correct | 6 ms | 11096 KB | Output is correct |
17 | Correct | 6 ms | 10844 KB | Output is correct |
18 | Correct | 6 ms | 10844 KB | Output is correct |
19 | Correct | 6 ms | 10844 KB | Output is correct |
20 | Correct | 9 ms | 11400 KB | Output is correct |
21 | Correct | 9 ms | 11356 KB | Output is correct |
22 | Correct | 43 ms | 14232 KB | Output is correct |
23 | Correct | 50 ms | 14224 KB | Output is correct |
24 | Correct | 42 ms | 14148 KB | Output is correct |
25 | Correct | 39 ms | 14024 KB | Output is correct |
26 | Correct | 42 ms | 15432 KB | Output is correct |
27 | Correct | 45 ms | 15360 KB | Output is correct |
28 | Correct | 40 ms | 15300 KB | Output is correct |
29 | Correct | 40 ms | 15300 KB | Output is correct |
30 | Correct | 41 ms | 15276 KB | Output is correct |
31 | Correct | 41 ms | 15464 KB | Output is correct |
32 | Correct | 45 ms | 15324 KB | Output is correct |
33 | Correct | 40 ms | 15276 KB | Output is correct |
34 | Correct | 40 ms | 15304 KB | Output is correct |
35 | Correct | 6 ms | 10844 KB | Output is correct |
36 | Correct | 6 ms | 10840 KB | Output is correct |
37 | Correct | 42 ms | 15280 KB | Output is correct |
38 | Correct | 42 ms | 15300 KB | Output is correct |
39 | Correct | 51 ms | 15272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11044 KB | Output is correct |
2 | Correct | 5 ms | 11092 KB | Output is correct |
3 | Correct | 5 ms | 10844 KB | Output is correct |
4 | Correct | 6 ms | 10844 KB | Output is correct |
5 | Correct | 58 ms | 19468 KB | Output is correct |
6 | Correct | 48 ms | 16084 KB | Output is correct |
7 | Correct | 61 ms | 20772 KB | Output is correct |
8 | Correct | 42 ms | 15532 KB | Output is correct |
9 | Correct | 58 ms | 20932 KB | Output is correct |
10 | Correct | 53 ms | 17848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10844 KB | Output is correct |
2 | Correct | 5 ms | 10844 KB | Output is correct |
3 | Correct | 6 ms | 10844 KB | Output is correct |
4 | Correct | 6 ms | 10872 KB | Output is correct |
5 | Correct | 5 ms | 10844 KB | Output is correct |
6 | Correct | 5 ms | 10844 KB | Output is correct |
7 | Correct | 6 ms | 10844 KB | Output is correct |
8 | Correct | 6 ms | 10844 KB | Output is correct |
9 | Correct | 6 ms | 10844 KB | Output is correct |
10 | Correct | 6 ms | 10844 KB | Output is correct |
11 | Correct | 5 ms | 10844 KB | Output is correct |
12 | Correct | 5 ms | 10840 KB | Output is correct |
13 | Correct | 8 ms | 10948 KB | Output is correct |
14 | Correct | 7 ms | 10844 KB | Output is correct |
15 | Correct | 6 ms | 10844 KB | Output is correct |
16 | Correct | 6 ms | 10844 KB | Output is correct |
17 | Correct | 5 ms | 10840 KB | Output is correct |
18 | Correct | 6 ms | 10840 KB | Output is correct |
19 | Correct | 6 ms | 10840 KB | Output is correct |
20 | Correct | 6 ms | 10844 KB | Output is correct |
21 | Correct | 6 ms | 10844 KB | Output is correct |
22 | Correct | 6 ms | 11096 KB | Output is correct |
23 | Correct | 5 ms | 10844 KB | Output is correct |
24 | Correct | 6 ms | 11096 KB | Output is correct |
25 | Correct | 6 ms | 10844 KB | Output is correct |
26 | Correct | 6 ms | 10844 KB | Output is correct |
27 | Correct | 6 ms | 10768 KB | Output is correct |
28 | Correct | 6 ms | 10844 KB | Output is correct |
29 | Correct | 7 ms | 10892 KB | Output is correct |
30 | Correct | 6 ms | 10844 KB | Output is correct |
31 | Correct | 6 ms | 10844 KB | Output is correct |
32 | Correct | 6 ms | 10844 KB | Output is correct |
33 | Correct | 6 ms | 10844 KB | Output is correct |
34 | Correct | 5 ms | 10844 KB | Output is correct |
35 | Correct | 6 ms | 10844 KB | Output is correct |
36 | Correct | 6 ms | 10844 KB | Output is correct |
37 | Correct | 6 ms | 10840 KB | Output is correct |
38 | Correct | 6 ms | 10844 KB | Output is correct |
39 | Correct | 6 ms | 10844 KB | Output is correct |
40 | Correct | 7 ms | 10844 KB | Output is correct |
41 | Correct | 6 ms | 10840 KB | Output is correct |
42 | Correct | 6 ms | 10840 KB | Output is correct |
43 | Correct | 6 ms | 11096 KB | Output is correct |
44 | Correct | 6 ms | 11096 KB | Output is correct |
45 | Correct | 6 ms | 10840 KB | Output is correct |
46 | Correct | 6 ms | 10844 KB | Output is correct |
47 | Correct | 6 ms | 10840 KB | Output is correct |
48 | Correct | 6 ms | 10844 KB | Output is correct |
49 | Correct | 6 ms | 10960 KB | Output is correct |
50 | Correct | 6 ms | 10844 KB | Output is correct |
51 | Correct | 6 ms | 10844 KB | Output is correct |
52 | Correct | 6 ms | 10840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10844 KB | Output is correct |
2 | Correct | 5 ms | 10844 KB | Output is correct |
3 | Correct | 6 ms | 10844 KB | Output is correct |
4 | Correct | 6 ms | 10872 KB | Output is correct |
5 | Correct | 5 ms | 10844 KB | Output is correct |
6 | Correct | 5 ms | 10844 KB | Output is correct |
7 | Correct | 6 ms | 10844 KB | Output is correct |
8 | Correct | 6 ms | 10844 KB | Output is correct |
9 | Correct | 6 ms | 10844 KB | Output is correct |
10 | Correct | 6 ms | 10844 KB | Output is correct |
11 | Correct | 5 ms | 10844 KB | Output is correct |
12 | Correct | 5 ms | 10840 KB | Output is correct |
13 | Correct | 8 ms | 10948 KB | Output is correct |
14 | Correct | 7 ms | 10844 KB | Output is correct |
15 | Correct | 6 ms | 10844 KB | Output is correct |
16 | Correct | 6 ms | 10844 KB | Output is correct |
17 | Correct | 5 ms | 10840 KB | Output is correct |
18 | Correct | 6 ms | 10840 KB | Output is correct |
19 | Correct | 6 ms | 10840 KB | Output is correct |
20 | Correct | 6 ms | 10844 KB | Output is correct |
21 | Correct | 6 ms | 10844 KB | Output is correct |
22 | Correct | 6 ms | 11096 KB | Output is correct |
23 | Correct | 5 ms | 10844 KB | Output is correct |
24 | Correct | 6 ms | 11096 KB | Output is correct |
25 | Correct | 6 ms | 10844 KB | Output is correct |
26 | Correct | 6 ms | 10844 KB | Output is correct |
27 | Correct | 6 ms | 10768 KB | Output is correct |
28 | Correct | 6 ms | 10844 KB | Output is correct |
29 | Correct | 7 ms | 10892 KB | Output is correct |
30 | Correct | 6 ms | 10844 KB | Output is correct |
31 | Correct | 6 ms | 10844 KB | Output is correct |
32 | Correct | 6 ms | 10844 KB | Output is correct |
33 | Correct | 6 ms | 10844 KB | Output is correct |
34 | Correct | 5 ms | 10844 KB | Output is correct |
35 | Correct | 6 ms | 10844 KB | Output is correct |
36 | Correct | 6 ms | 10844 KB | Output is correct |
37 | Correct | 6 ms | 10844 KB | Output is correct |
38 | Correct | 6 ms | 10844 KB | Output is correct |
39 | Correct | 6 ms | 10840 KB | Output is correct |
40 | Correct | 6 ms | 10844 KB | Output is correct |
41 | Correct | 5 ms | 10844 KB | Output is correct |
42 | Correct | 6 ms | 10844 KB | Output is correct |
43 | Correct | 6 ms | 10844 KB | Output is correct |
44 | Correct | 6 ms | 10840 KB | Output is correct |
45 | Correct | 6 ms | 10844 KB | Output is correct |
46 | Correct | 6 ms | 10844 KB | Output is correct |
47 | Correct | 6 ms | 10844 KB | Output is correct |
48 | Correct | 6 ms | 10844 KB | Output is correct |
49 | Correct | 6 ms | 10844 KB | Output is correct |
50 | Correct | 6 ms | 11096 KB | Output is correct |
51 | Correct | 6 ms | 10844 KB | Output is correct |
52 | Correct | 6 ms | 10844 KB | Output is correct |
53 | Correct | 6 ms | 10844 KB | Output is correct |
54 | Correct | 9 ms | 11400 KB | Output is correct |
55 | Correct | 9 ms | 11356 KB | Output is correct |
56 | Correct | 43 ms | 14232 KB | Output is correct |
57 | Correct | 50 ms | 14224 KB | Output is correct |
58 | Correct | 42 ms | 14148 KB | Output is correct |
59 | Correct | 39 ms | 14024 KB | Output is correct |
60 | Correct | 42 ms | 15432 KB | Output is correct |
61 | Correct | 45 ms | 15360 KB | Output is correct |
62 | Correct | 40 ms | 15300 KB | Output is correct |
63 | Correct | 40 ms | 15300 KB | Output is correct |
64 | Correct | 41 ms | 15276 KB | Output is correct |
65 | Correct | 41 ms | 15464 KB | Output is correct |
66 | Correct | 45 ms | 15324 KB | Output is correct |
67 | Correct | 40 ms | 15276 KB | Output is correct |
68 | Correct | 40 ms | 15304 KB | Output is correct |
69 | Correct | 6 ms | 10844 KB | Output is correct |
70 | Correct | 6 ms | 10840 KB | Output is correct |
71 | Correct | 42 ms | 15280 KB | Output is correct |
72 | Correct | 42 ms | 15300 KB | Output is correct |
73 | Correct | 51 ms | 15272 KB | Output is correct |
74 | Correct | 6 ms | 11044 KB | Output is correct |
75 | Correct | 5 ms | 11092 KB | Output is correct |
76 | Correct | 5 ms | 10844 KB | Output is correct |
77 | Correct | 6 ms | 10844 KB | Output is correct |
78 | Correct | 58 ms | 19468 KB | Output is correct |
79 | Correct | 48 ms | 16084 KB | Output is correct |
80 | Correct | 61 ms | 20772 KB | Output is correct |
81 | Correct | 42 ms | 15532 KB | Output is correct |
82 | Correct | 58 ms | 20932 KB | Output is correct |
83 | Correct | 53 ms | 17848 KB | Output is correct |
84 | Correct | 6 ms | 10840 KB | Output is correct |
85 | Correct | 6 ms | 10844 KB | Output is correct |
86 | Correct | 6 ms | 10844 KB | Output is correct |
87 | Correct | 7 ms | 10844 KB | Output is correct |
88 | Correct | 6 ms | 10840 KB | Output is correct |
89 | Correct | 6 ms | 10840 KB | Output is correct |
90 | Correct | 6 ms | 11096 KB | Output is correct |
91 | Correct | 6 ms | 11096 KB | Output is correct |
92 | Correct | 6 ms | 10840 KB | Output is correct |
93 | Correct | 6 ms | 10844 KB | Output is correct |
94 | Correct | 6 ms | 10840 KB | Output is correct |
95 | Correct | 6 ms | 10844 KB | Output is correct |
96 | Correct | 6 ms | 10960 KB | Output is correct |
97 | Correct | 6 ms | 10844 KB | Output is correct |
98 | Correct | 6 ms | 10844 KB | Output is correct |
99 | Correct | 6 ms | 10840 KB | Output is correct |
100 | Correct | 6 ms | 10844 KB | Output is correct |
101 | Correct | 11 ms | 11976 KB | Output is correct |
102 | Correct | 10 ms | 11612 KB | Output is correct |
103 | Correct | 64 ms | 20764 KB | Output is correct |
104 | Correct | 57 ms | 20948 KB | Output is correct |
105 | Correct | 61 ms | 18116 KB | Output is correct |
106 | Correct | 58 ms | 20840 KB | Output is correct |
107 | Correct | 49 ms | 16144 KB | Output is correct |
108 | Correct | 55 ms | 16568 KB | Output is correct |
109 | Correct | 47 ms | 15812 KB | Output is correct |
110 | Correct | 40 ms | 15440 KB | Output is correct |
111 | Correct | 59 ms | 20164 KB | Output is correct |
112 | Correct | 60 ms | 19404 KB | Output is correct |
113 | Correct | 50 ms | 16080 KB | Output is correct |
114 | Correct | 58 ms | 20732 KB | Output is correct |
115 | Correct | 57 ms | 20928 KB | Output is correct |