Submission #971155

#TimeUsernameProblemLanguageResultExecution timeMemory
971155yellowtoadArranging Shoes (IOI19_shoes)C++17
25 / 100
218 ms280260 KiB
#include "shoes.h" #include <iostream> #include <queue> #define f first #define s second #define int long long using namespace std; int p[200010], cnt, nxt, tmp[200010]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> ll, rr; queue<int> l[200010]; queue<int> r[200010]; void merge(int l, int r) { if (l >= r) return; int mid = (l+r)/2; merge(l,mid); merge(mid+1,r); int x = l, y = mid+1; for (int i = l; i <= r; i++) { if ((y > r) || ((x <= mid) && (p[x] < p[y]))) tmp[i] = p[x++]; else { cnt += mid-x+1; tmp[i] = p[y++]; } } for (int i = l; i <= r; i++) p[i] = tmp[i]; } long long count_swaps(std::vector<signed> a) { for (int i = 0; i < a.size(); i++) { if (a[i] < 0) { ll.push({i,-a[i]}); l[-a[i]].push(i); } else { rr.push({i,a[i]}); r[a[i]].push(i); } } for (int i = 0; i < a.size(); i++) { if (i%2 == 0) { if (ll.top() < rr.top()) { p[ll.top().f] = i; nxt = ll.top().s; ll.pop(); l[nxt].pop(); } else { nxt = rr.top().s; rr.pop(); p[l[nxt].front()] = i; l[nxt].pop(); } } else { p[r[nxt].front()] = i; r[nxt].pop(); } } merge(0,a.size()-1); return cnt; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
shoes.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < a.size(); 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...