제출 #305509

#제출 시각아이디문제언어결과실행 시간메모리
305509knon0501Arranging Shoes (IOI19_shoes)C++14
100 / 100
355 ms275184 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int MX=2e5+5; int nn; queue<int> a[MX],b[MX]; int bit[MX*2]; int n; int f(int x){ int ret=0; for(int i=x ; i>=1 ; i-=(i&-i))ret+=bit[i]; return ret; } void upd(int x){ for(int i=x ; i<=n ; i+=(i&-i))bit[i]++; } long long count_swaps(std::vector<int> s) { int i,j; long long ans=0; n=s.size(); for(i=0 ; i<n ; i++){ if(s[i]>0) a[s[i]].push(i); else b[-s[i]].push(i); } vector<pair<int,int>> v; for(i=1 ; i*2<=n ; i++){ while(!a[i].empty()){ v.push_back({a[i].front(),b[i].front()}); a[i].pop(); b[i].pop(); } } sort(v.begin(),v.end(),[&](pair<int,int> q,pair<int,int> w){ return q.first+q.second-(q.first>q.second)>w.first+w.second-(w.first>w.second); }); for(i=0 ; i<n ; i+=2){ auto k=v.back(); v.pop_back(); ans+=k.first+k.second-(k.first>k.second)+f(n)*2-f(k.first+1)-f(k.second+1)-i*2; upd(k.first+1); upd(k.second+1); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:18:11: warning: unused variable 'j' [-Wunused-variable]
   18 |     int 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...