Submission #525966

#TimeUsernameProblemLanguageResultExecution timeMemory
525966HanksburgerArranging Shoes (IOI19_shoes)C++17
10 / 100
43 ms15836 KiB
#include <bits/stdc++.h> using namespace std; vector<int> pos[100005]; int a[100005], cnt; long long f(int l, int r) { if (l==r) return 0; int mid=(l+r)/2, index=(l+r)/2+1; long long res=f(l, mid)+f(mid+1, r); for (int i=l; i<=mid; i++) { while (index<=r && a[i]>a[index]) index++; res+=index-mid-1; } sort(a+l, a+r+1); return res; } long long count_swaps(vector<int> v) { for (int i=0; i<v.size(); i++) if (v[i]>0) pos[v[i]].push_back(i); for (int i=1; i<=v.size(); i++) reverse(pos[i].begin(), pos[i].end()); for (int i=0; i<v.size(); i++) { if (v[i]<0) { cnt+=2; a[i]=cnt-1; a[pos[-v[i]][pos[-v[i]].size()-1]]=cnt; pos[-v[i]].pop_back(); } } return f(0, cnt-1); }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i=0; i<v.size(); i++)
      |                ~^~~~~~~~~
shoes.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i=1; i<=v.size(); i++)
      |                ~^~~~~~~~~~
shoes.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i=0; i<v.size(); i++)
      |                ~^~~~~~~~~

Subtask 110 / 10

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 20 / 20

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 30 / 20

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 40 / 15

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 50 / 20

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 60 / 15

#Verdict Execution timeMemoryGrader output
Fetching results...