Submission #971143

#TimeUsernameProblemLanguageResultExecution timeMemory
971143yellowtoadArranging Shoes (IOI19_shoes)C++17
10 / 100
116 ms145616 KiB
#include "shoes.h" #include <iostream> #include <queue> #define f first #define s second using namespace std; int p[100010], cnt, nxt, tmp[100010]; queue<pair<int,int>> l; queue<int> r[100010]; 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<int> a) { for (int i = 0; i < a.size(); i++) { if (a[i] < 0) l.push({i,-a[i]}); else r[a[i]].push(i); } for (int i = 0; i < a.size(); i++) { if (i%2 == 0) { p[l.front().f] = i; nxt = l.front().s; l.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:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
shoes.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  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...