# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158391 | 2019-10-16T21:27:50 Z | nickmet2004 | Arranging Shoes (IOI19_shoes) | C++14 | 161 ms | 135160 KB |
#include<bits/stdc++.h> //#include<shoes.h> using namespace std; const int NAX = 1e5 + 5; const int l = 1e5 + 5; int N; // fenwick tree to count range sums (+0 , +1 , +2) int f[2 * NAX + 1]; void update(int idx , int u){ ++idx; while(idx <= N){ f[idx] += u; idx += idx & (-idx); } } long long sum(int idx){ long long sum = 0; ++idx; while(idx){ sum += f[idx]; idx -= idx & (-idx); } return sum; } queue<int> q[2 * NAX + 200]; long long count_swaps(vector<int> S){ N = S.size(); long long ans = 0; // update BIT for(int i = 0; i < N; ++i){ update(i , 1); } for(int i = 0; i < N; ++i){ int x = abs(S[i]); int k = S[i]; if(!q[k + l].empty()){ ans += (sum(i) - (q[k + l].front() - 1) - 1); if(k > 0){ --ans; } update(i , -1); update(q[k + l].front() , 1); q[k + l].pop(); } else { // q[k * -1 + l] because its opposite is the same as the next x // k * -1 + l == next_x(k + l) q[k * -1 + l].push(i); } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 135160 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 135160 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 135160 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 159 ms | 135100 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 135160 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 135160 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |