제출 #852307

#제출 시각아이디문제언어결과실행 시간메모리
852307teo_thrashArranging Shoes (IOI19_shoes)C++14
100 / 100
57 ms12852 KiB
#include "shoes.h" #include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn=2e5+5; int bit[maxn]; void update(int idx, int delta){ for(; idx<maxn; idx += (idx & -idx)){ bit[idx]+=delta; } } ll query(int idx){ ll sum=0; for(; idx>0; idx -= (idx & -idx)){ sum+=bit[idx]; } return sum; } ll query(int l, int r){ return query(r-1)-query(l); } ll count_swaps(vector<int> a){ ll ans=0; vector<pii> shoes[maxn]; int n=a.size()/2; for(int i=0; i<a.size(); i++){ shoes[abs(a[i])].pb({a[i], i}); } vector<pii> pairs; for(int i=1; i<=a.size()/2; i++){ sort(shoes[i].begin(), shoes[i].end()); for(int j=0; j<shoes[i].size()/2; j++){ int l=shoes[i][j].second; int r=shoes[i][j + (shoes[i].size()/2) ].second; if(l>r){ swap(l, r); ans++; } pairs.pb({l+1, r+1}); } } for(int i=1; i<=a.size(); i++){ update(i, 1); } sort(pairs.begin(), pairs.end()); for(auto p: pairs){ ans+=query(p.first, p.second); update(p.first, -1); update(p.second, -1); } return ans; }

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

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0; i<a.size(); i++){
      |                  ~^~~~~~~~~
shoes.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=1; i<=a.size()/2; i++){
      |                  ~^~~~~~~~~~~~
shoes.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0; j<shoes[i].size()/2; j++){
      |                      ~^~~~~~~~~~~~~~~~~~
shoes.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=1; i<=a.size(); i++){
      |                  ~^~~~~~~~~~
shoes.cpp:34:9: warning: unused variable 'n' [-Wunused-variable]
   34 |     int n=a.size()/2;
      |         ^
#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...