Submission #944806

#TimeUsernameProblemLanguageResultExecution timeMemory
944806PenguinsAreCuteArranging Shoes (IOI19_shoes)C++17
100 / 100
68 ms16656 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; using ll = long long; struct ft { vector<int> v; int n; ft(int _n): n(_n) {v.resize(n+1,0);} inline int lsb(int x) {return x&(-x);} void up(int x, int u) { for(;x<=n;x+=lsb(x)) v[x]+=u; } int qry(int x) { ll ans = 0; for(;x;x-=lsb(x)) ans += v[x]; return ans; } }; long long count_swaps(std::vector<int> s) { int n = s.size() / 2; vector<int> v, posP[n+1], posN[n+1]; for(int i=0;i<2*n;i++) { if(s[i]<0) posN[-s[i]].push_back(i); else posP[s[i]].push_back(i); } vector<pair<int,int>> vec; for(int i=1;i<=n;i++) for(int j=0;j<posN[i].size();j++) vec.push_back({posN[i][j],posP[i][j]}); sort(vec.begin(),vec.end(),[](pair<int,int> a, pair<int,int> b) {return a.first+a.second<b.first+b.second;}); v.resize(2*n); for(int i=0;i<2*n;i+=2) { v[i] = vec[i>>1].first; v[i+1] = vec[i>>1].second; } ll ans = 0; ft fenwick(2*n); for(int i=2*n;i--;) { ans += fenwick.qry(v[i]); fenwick.up(v[i]+1,1); } return ans; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=1;i<=n;i++) for(int j=0;j<posN[i].size();j++) vec.push_back({posN[i][j],posP[i][j]});
      |                                    ~^~~~~~~~~~~~~~~
#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...