Submission #153492

#TimeUsernameProblemLanguageResultExecution timeMemory
153492myungwooArranging Shoes (IOI19_shoes)C++14
0 / 100
135 ms134936 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; #define MAXN 100005 typedef long long lld; int N; int A[MAXN], bit[MAXN]; stack <int> L[MAXN], R[MAXN], order; void add(int n, int v){ for (;n<=N;n+=n&-n) bit[n] += v; } int get(int n) { int ret = 0; for (;n;n^=n&-n) ret += bit[n]; return ret; } int move(int a, int b) { // a -> b add(a, 1); printf("%d %d\n", a-get(a-1), b); return b-(a-get(a-1)); } lld proc(vector<int> arr) { N = arr.size(); for (int i=1;i<=N;i++) A[i] = arr[i-1], bit[i] = 0; for (int i=1;i<=N;i++){ if (A[i] < 0) L[-A[i]].push(i); if (A[i] > 0){ R[A[i]].push(i); order.push(A[i]); } } lld total = 0; int pos = N; while (!order.empty()){ int t = order.top(); total += move(R[t].top(), pos); total += move(L[t].top(), pos-1); order.pop(); R[t].pop(); L[t].pop(); pos -= 2; } return total; } lld count_swaps(vector<int> arr) { lld ans = proc(arr); reverse(arr.begin(), arr.end()); for (int i=0;i<arr.size();i++) arr[i] = -arr[i]; ans = min(ans, proc(arr)); return ans; }

Compilation message (stderr)

shoes.cpp: In function 'lld count_swaps(std::vector<int>)':
shoes.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<arr.size();i++) arr[i] = -arr[i];
               ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...