제출 #971156

#제출 시각아이디문제언어결과실행 시간메모리
971156yellowtoadArranging Shoes (IOI19_shoes)C++17
100 / 100
238 ms283584 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], lll[200010], rrr[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++) { while (lll[ll.top().s]) { lll[ll.top().s]--; ll.pop(); } while (rrr[rr.top().s]) { rrr[rr.top().s]--; rr.pop(); } if (i%2 == 0) { if (ll.top() < rr.top()) { p[ll.top().f] = i; nxt = ll.top().s; ll.pop(); l[nxt].pop(); rrr[nxt]++; } else { nxt = rr.top().s; rr.pop(); p[l[nxt].front()] = i; l[nxt].pop(); lll[nxt]++; } } else { p[r[nxt].front()] = i; r[nxt].pop(); } } merge(0,a.size()-1); return cnt; }

컴파일 시 표준 에러 (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...