# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
965386 | 2024-04-18T12:21:49 Z | akacool445k | Arranging Shoes (IOI19_shoes) | C++14 | 1 ms | 504 KB |
#include <queue> #include <iostream> #include "shoes.h" using namespace std; int N; int bit[200001]; int query(int i) { int res = 0; while (i > 0) { res += bit[i]; i -= (i & -i); } return res; } void update(int i) { while (i <= N) { bit[i] = 0; i += (i & -i); } } long long count_swaps(vector<int> s) { long long n = s.size(); long long ans = 0; N = n; queue<int> a[n / 2 + 1], b[n / 2 + 1]; for (int i = 0; i < n; i++) { if (s[i] < 0) a[-s[i]].push(i); else b[s[i]].push(i); } vector<int> c(n, 1); for (int i = 0; i < n; i++) { if (c[i] == 0) continue; int ss = 0; int x = s[i]; int j = i; if (x < 0) { int y = -x; j = b[y].front(); b[y].pop(); a[y].pop(); } else { j = a[x].front(); a[x].pop(); b[x].pop(); } update(i + 1); update(j + 1); ans += query(j + 1); c[j] = 0; if (x > 0) ans++; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 344 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 344 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 344 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 344 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |