# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
143549 | 2019-08-14T14:33:50 Z | abeker | Arranging Shoes (IOI19_shoes) | C++17 | 208 ms | 70108 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 5; struct fenwick { vector <int> fen; fenwick(int n) { fen.resize(n + 5); } void update(int x) { for (x++; x < fen.size(); x += x & -x) fen[x]++; } int get(int x) { int res = 0; for (x++; x; x -= x & -x) res += fen[x]; return res; } }; int N; vector <int> lft[MAXN], rig[MAXN]; vector <int> perm[MAXN], pos[MAXN]; ll inversions(vector <int> v) { reverse(v.begin(), v.end()); fenwick tmp(v.size()); ll res = 0; for (auto it : v) { res += tmp.get(it); tmp.update(it); } return res; } ll count_swaps(vector <int> shoes) { N = shoes.size(); vector <int> todo(N, -1); for (int i = 0; i < N; i++) { int sz = abs(shoes[i]); if (shoes[i] < 0) { perm[sz].push_back(2 * lft[sz].size()); lft[sz].push_back(i); } else { perm[sz].push_back(2 * rig[sz].size() + 1); rig[sz].push_back(i); } pos[sz].push_back(i); } ll sol = 0; for (int i = 0; i < N; i++) { sol += inversions(perm[i]); for (int j = 0; j < lft[i].size(); j++) todo[max(lft[i][j], rig[i][j])] = min(lft[i][j], rig[i][j]); } fenwick fin(N); for (int i = 0; i < N; i++) if (todo[i] != -1) { sol += fin.get(N) - fin.get(todo[i]); fin.update(todo[i]); fin.update(i); } for (int i = 0; i < N; i++) { fenwick tmp(pos[i].size()); for (auto it : pos[i]) if (todo[it] != -1) { sol -= tmp.get(pos[i].size()) - tmp.get(todo[it]); tmp.update(todo[it]); tmp.update(it); } } return sol; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 19 ms | 19064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 19 ms | 19064 KB | Output is correct |
3 | Correct | 19 ms | 19064 KB | Output is correct |
4 | Correct | 20 ms | 19064 KB | Output is correct |
5 | Correct | 24 ms | 19064 KB | Output is correct |
6 | Correct | 19 ms | 19064 KB | Output is correct |
7 | Correct | 19 ms | 19064 KB | Output is correct |
8 | Correct | 20 ms | 19064 KB | Output is correct |
9 | Correct | 19 ms | 19064 KB | Output is correct |
10 | Correct | 20 ms | 19068 KB | Output is correct |
11 | Correct | 19 ms | 19040 KB | Output is correct |
12 | Correct | 18 ms | 19064 KB | Output is correct |
13 | Correct | 20 ms | 19064 KB | Output is correct |
14 | Incorrect | 20 ms | 19192 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 19 ms | 19064 KB | Output is correct |
3 | Correct | 19 ms | 19092 KB | Output is correct |
4 | Correct | 19 ms | 19124 KB | Output is correct |
5 | Correct | 22 ms | 19064 KB | Output is correct |
6 | Correct | 23 ms | 19064 KB | Output is correct |
7 | Correct | 23 ms | 19064 KB | Output is correct |
8 | Correct | 25 ms | 19064 KB | Output is correct |
9 | Correct | 19 ms | 19064 KB | Output is correct |
10 | Correct | 19 ms | 19064 KB | Output is correct |
11 | Correct | 19 ms | 19064 KB | Output is correct |
12 | Correct | 19 ms | 19064 KB | Output is correct |
13 | Correct | 19 ms | 19076 KB | Output is correct |
14 | Correct | 19 ms | 19064 KB | Output is correct |
15 | Correct | 19 ms | 19064 KB | Output is correct |
16 | Correct | 20 ms | 19152 KB | Output is correct |
17 | Correct | 20 ms | 19192 KB | Output is correct |
18 | Correct | 20 ms | 19172 KB | Output is correct |
19 | Correct | 21 ms | 19192 KB | Output is correct |
20 | Correct | 27 ms | 19880 KB | Output is correct |
21 | Correct | 27 ms | 19932 KB | Output is correct |
22 | Correct | 97 ms | 25400 KB | Output is correct |
23 | Correct | 88 ms | 26208 KB | Output is correct |
24 | Correct | 96 ms | 25944 KB | Output is correct |
25 | Correct | 90 ms | 25952 KB | Output is correct |
26 | Correct | 96 ms | 25820 KB | Output is correct |
27 | Correct | 85 ms | 26176 KB | Output is correct |
28 | Correct | 91 ms | 26172 KB | Output is correct |
29 | Correct | 90 ms | 25952 KB | Output is correct |
30 | Correct | 90 ms | 25956 KB | Output is correct |
31 | Correct | 96 ms | 25784 KB | Output is correct |
32 | Correct | 90 ms | 25952 KB | Output is correct |
33 | Correct | 89 ms | 25952 KB | Output is correct |
34 | Correct | 91 ms | 25936 KB | Output is correct |
35 | Correct | 19 ms | 19064 KB | Output is correct |
36 | Correct | 20 ms | 19064 KB | Output is correct |
37 | Correct | 92 ms | 25952 KB | Output is correct |
38 | Correct | 93 ms | 25952 KB | Output is correct |
39 | Correct | 92 ms | 25948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 23 ms | 19064 KB | Output is correct |
3 | Correct | 19 ms | 19068 KB | Output is correct |
4 | Correct | 25 ms | 19036 KB | Output is correct |
5 | Runtime error | 208 ms | 70108 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 19 ms | 19064 KB | Output is correct |
3 | Correct | 19 ms | 19064 KB | Output is correct |
4 | Correct | 20 ms | 19064 KB | Output is correct |
5 | Correct | 24 ms | 19064 KB | Output is correct |
6 | Correct | 19 ms | 19064 KB | Output is correct |
7 | Correct | 19 ms | 19064 KB | Output is correct |
8 | Correct | 20 ms | 19064 KB | Output is correct |
9 | Correct | 19 ms | 19064 KB | Output is correct |
10 | Correct | 20 ms | 19068 KB | Output is correct |
11 | Correct | 19 ms | 19040 KB | Output is correct |
12 | Correct | 18 ms | 19064 KB | Output is correct |
13 | Correct | 20 ms | 19064 KB | Output is correct |
14 | Incorrect | 20 ms | 19192 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19064 KB | Output is correct |
2 | Correct | 19 ms | 19064 KB | Output is correct |
3 | Correct | 19 ms | 19064 KB | Output is correct |
4 | Correct | 20 ms | 19064 KB | Output is correct |
5 | Correct | 24 ms | 19064 KB | Output is correct |
6 | Correct | 19 ms | 19064 KB | Output is correct |
7 | Correct | 19 ms | 19064 KB | Output is correct |
8 | Correct | 20 ms | 19064 KB | Output is correct |
9 | Correct | 19 ms | 19064 KB | Output is correct |
10 | Correct | 20 ms | 19068 KB | Output is correct |
11 | Correct | 19 ms | 19040 KB | Output is correct |
12 | Correct | 18 ms | 19064 KB | Output is correct |
13 | Correct | 20 ms | 19064 KB | Output is correct |
14 | Incorrect | 20 ms | 19192 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |