# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
832687 | 2023-08-21T13:50:11 Z | Marco_Escandon | Arranging Shoes (IOI19_shoes) | C++17 | 291 ms | 413420 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct st{ vector<ll> asd; void update(ll a, ll b) { for(a; a<asd.size(); a+=(a&(-a))) { asd[a]+=b; } } ll query(ll a) { ll cont=0; for(a; a>0; a-=(a&(-a))) { cont+=asd[a]; } return cont; } st(ll n) { asd.resize(2*n); } }; #define op -s[i]+n long long count_swaps(std::vector<int> s) { ll n= s.size(); vector<ll> inv(n,0); vector<queue<ll>> asd(n*3); for(int i=0; i<n; i++) asd[s[i]+n].push(i); ll cont=1; for(int i=0; i<n; i++) { if(s[i]!=0) { if(s[i]<0) { inv[i]=cont; asd[s[i]+n].pop(); cont++; inv[asd[op].front()]=cont; cont++; } else { inv[i]=cont+1; asd[s[i]+n].pop(); inv[asd[op].front()]=cont; cont+=2; } s[asd[op].front()]=0; asd[op].pop(); s[i]=0; } } st asdf(n); cont=0; /*for(auto i:inv) { cout<<i<<" "; } cout<<"\n";*/ for(int i=n-1; i>-1; i--) { cont+=asdf.query(inv[i]); asdf.update(inv[i],1); } return cont; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 300 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 300 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 300 KB | Output is correct |
17 | Correct | 1 ms | 300 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 212 KB | Output is correct |
22 | Correct | 1 ms | 304 KB | Output is correct |
23 | Correct | 1 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 296 KB | Output is correct |
25 | Correct | 0 ms | 300 KB | Output is correct |
26 | Correct | 0 ms | 296 KB | Output is correct |
27 | Correct | 0 ms | 212 KB | Output is correct |
28 | Correct | 1 ms | 308 KB | Output is correct |
29 | Correct | 1 ms | 212 KB | Output is correct |
30 | Correct | 0 ms | 216 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Correct | 0 ms | 212 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 304 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 724 KB | Output is correct |
17 | Correct | 1 ms | 1456 KB | Output is correct |
18 | Correct | 2 ms | 4308 KB | Output is correct |
19 | Correct | 2 ms | 4436 KB | Output is correct |
20 | Correct | 23 ms | 41528 KB | Output is correct |
21 | Correct | 24 ms | 41600 KB | Output is correct |
22 | Correct | 236 ms | 413352 KB | Output is correct |
23 | Correct | 228 ms | 413296 KB | Output is correct |
24 | Correct | 227 ms | 413388 KB | Output is correct |
25 | Correct | 218 ms | 413168 KB | Output is correct |
26 | Correct | 222 ms | 413320 KB | Output is correct |
27 | Correct | 236 ms | 413116 KB | Output is correct |
28 | Correct | 234 ms | 413356 KB | Output is correct |
29 | Correct | 229 ms | 413284 KB | Output is correct |
30 | Correct | 222 ms | 413392 KB | Output is correct |
31 | Correct | 222 ms | 413420 KB | Output is correct |
32 | Correct | 226 ms | 413344 KB | Output is correct |
33 | Correct | 220 ms | 413124 KB | Output is correct |
34 | Correct | 223 ms | 413376 KB | Output is correct |
35 | Correct | 0 ms | 300 KB | Output is correct |
36 | Correct | 0 ms | 212 KB | Output is correct |
37 | Correct | 229 ms | 413392 KB | Output is correct |
38 | Correct | 235 ms | 413260 KB | Output is correct |
39 | Correct | 230 ms | 413364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 232 ms | 411676 KB | Output is correct |
6 | Correct | 225 ms | 411648 KB | Output is correct |
7 | Correct | 279 ms | 411688 KB | Output is correct |
8 | Correct | 223 ms | 413388 KB | Output is correct |
9 | Correct | 244 ms | 411676 KB | Output is correct |
10 | Correct | 275 ms | 411696 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 300 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 300 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 300 KB | Output is correct |
17 | Correct | 1 ms | 300 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 212 KB | Output is correct |
22 | Correct | 1 ms | 304 KB | Output is correct |
23 | Correct | 1 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 296 KB | Output is correct |
25 | Correct | 0 ms | 300 KB | Output is correct |
26 | Correct | 0 ms | 296 KB | Output is correct |
27 | Correct | 0 ms | 212 KB | Output is correct |
28 | Correct | 1 ms | 308 KB | Output is correct |
29 | Correct | 1 ms | 212 KB | Output is correct |
30 | Correct | 0 ms | 216 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Correct | 0 ms | 212 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 0 ms | 212 KB | Output is correct |
37 | Correct | 0 ms | 300 KB | Output is correct |
38 | Correct | 0 ms | 468 KB | Output is correct |
39 | Correct | 1 ms | 724 KB | Output is correct |
40 | Correct | 1 ms | 1492 KB | Output is correct |
41 | Correct | 3 ms | 4308 KB | Output is correct |
42 | Correct | 2 ms | 4308 KB | Output is correct |
43 | Correct | 2 ms | 4400 KB | Output is correct |
44 | Correct | 2 ms | 4308 KB | Output is correct |
45 | Correct | 2 ms | 4308 KB | Output is correct |
46 | Correct | 2 ms | 4308 KB | Output is correct |
47 | Correct | 2 ms | 4308 KB | Output is correct |
48 | Correct | 3 ms | 4308 KB | Output is correct |
49 | Correct | 3 ms | 4308 KB | Output is correct |
50 | Correct | 3 ms | 4308 KB | Output is correct |
51 | Correct | 3 ms | 4360 KB | Output is correct |
52 | Correct | 2 ms | 4404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 300 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 300 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 300 KB | Output is correct |
17 | Correct | 1 ms | 300 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 212 KB | Output is correct |
22 | Correct | 1 ms | 304 KB | Output is correct |
23 | Correct | 1 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 296 KB | Output is correct |
25 | Correct | 0 ms | 300 KB | Output is correct |
26 | Correct | 0 ms | 296 KB | Output is correct |
27 | Correct | 0 ms | 212 KB | Output is correct |
28 | Correct | 1 ms | 308 KB | Output is correct |
29 | Correct | 1 ms | 212 KB | Output is correct |
30 | Correct | 0 ms | 216 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Correct | 0 ms | 212 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 0 ms | 212 KB | Output is correct |
37 | Correct | 0 ms | 212 KB | Output is correct |
38 | Correct | 0 ms | 212 KB | Output is correct |
39 | Correct | 0 ms | 212 KB | Output is correct |
40 | Correct | 0 ms | 212 KB | Output is correct |
41 | Correct | 1 ms | 212 KB | Output is correct |
42 | Correct | 0 ms | 212 KB | Output is correct |
43 | Correct | 0 ms | 212 KB | Output is correct |
44 | Correct | 1 ms | 304 KB | Output is correct |
45 | Correct | 0 ms | 212 KB | Output is correct |
46 | Correct | 0 ms | 212 KB | Output is correct |
47 | Correct | 0 ms | 212 KB | Output is correct |
48 | Correct | 0 ms | 212 KB | Output is correct |
49 | Correct | 1 ms | 468 KB | Output is correct |
50 | Correct | 1 ms | 724 KB | Output is correct |
51 | Correct | 1 ms | 1456 KB | Output is correct |
52 | Correct | 2 ms | 4308 KB | Output is correct |
53 | Correct | 2 ms | 4436 KB | Output is correct |
54 | Correct | 23 ms | 41528 KB | Output is correct |
55 | Correct | 24 ms | 41600 KB | Output is correct |
56 | Correct | 236 ms | 413352 KB | Output is correct |
57 | Correct | 228 ms | 413296 KB | Output is correct |
58 | Correct | 227 ms | 413388 KB | Output is correct |
59 | Correct | 218 ms | 413168 KB | Output is correct |
60 | Correct | 222 ms | 413320 KB | Output is correct |
61 | Correct | 236 ms | 413116 KB | Output is correct |
62 | Correct | 234 ms | 413356 KB | Output is correct |
63 | Correct | 229 ms | 413284 KB | Output is correct |
64 | Correct | 222 ms | 413392 KB | Output is correct |
65 | Correct | 222 ms | 413420 KB | Output is correct |
66 | Correct | 226 ms | 413344 KB | Output is correct |
67 | Correct | 220 ms | 413124 KB | Output is correct |
68 | Correct | 223 ms | 413376 KB | Output is correct |
69 | Correct | 0 ms | 300 KB | Output is correct |
70 | Correct | 0 ms | 212 KB | Output is correct |
71 | Correct | 229 ms | 413392 KB | Output is correct |
72 | Correct | 235 ms | 413260 KB | Output is correct |
73 | Correct | 230 ms | 413364 KB | Output is correct |
74 | Correct | 0 ms | 212 KB | Output is correct |
75 | Correct | 0 ms | 212 KB | Output is correct |
76 | Correct | 0 ms | 212 KB | Output is correct |
77 | Correct | 0 ms | 212 KB | Output is correct |
78 | Correct | 232 ms | 411676 KB | Output is correct |
79 | Correct | 225 ms | 411648 KB | Output is correct |
80 | Correct | 279 ms | 411688 KB | Output is correct |
81 | Correct | 223 ms | 413388 KB | Output is correct |
82 | Correct | 244 ms | 411676 KB | Output is correct |
83 | Correct | 275 ms | 411696 KB | Output is correct |
84 | Correct | 0 ms | 300 KB | Output is correct |
85 | Correct | 0 ms | 468 KB | Output is correct |
86 | Correct | 1 ms | 724 KB | Output is correct |
87 | Correct | 1 ms | 1492 KB | Output is correct |
88 | Correct | 3 ms | 4308 KB | Output is correct |
89 | Correct | 2 ms | 4308 KB | Output is correct |
90 | Correct | 2 ms | 4400 KB | Output is correct |
91 | Correct | 2 ms | 4308 KB | Output is correct |
92 | Correct | 2 ms | 4308 KB | Output is correct |
93 | Correct | 2 ms | 4308 KB | Output is correct |
94 | Correct | 2 ms | 4308 KB | Output is correct |
95 | Correct | 3 ms | 4308 KB | Output is correct |
96 | Correct | 3 ms | 4308 KB | Output is correct |
97 | Correct | 3 ms | 4308 KB | Output is correct |
98 | Correct | 3 ms | 4360 KB | Output is correct |
99 | Correct | 2 ms | 4404 KB | Output is correct |
100 | Correct | 2 ms | 4308 KB | Output is correct |
101 | Correct | 24 ms | 41400 KB | Output is correct |
102 | Correct | 23 ms | 41428 KB | Output is correct |
103 | Correct | 243 ms | 411672 KB | Output is correct |
104 | Correct | 249 ms | 411720 KB | Output is correct |
105 | Correct | 259 ms | 411808 KB | Output is correct |
106 | Correct | 272 ms | 411692 KB | Output is correct |
107 | Correct | 234 ms | 411724 KB | Output is correct |
108 | Correct | 234 ms | 411596 KB | Output is correct |
109 | Correct | 225 ms | 413316 KB | Output is correct |
110 | Correct | 220 ms | 413388 KB | Output is correct |
111 | Correct | 233 ms | 411700 KB | Output is correct |
112 | Correct | 270 ms | 411596 KB | Output is correct |
113 | Correct | 291 ms | 411724 KB | Output is correct |
114 | Correct | 241 ms | 411664 KB | Output is correct |
115 | Correct | 263 ms | 411692 KB | Output is correct |