제출 #294960

#제출 시각아이디문제언어결과실행 시간메모리
294960theStaticMindArranging Shoes (IOI19_shoes)C++14
100 / 100
133 ms23568 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; struct Fenwick{ vector<int> bit; Fenwick(){ bit = vector<int> (1e6, 0); } void modify(int j, int v){ j++; for(;j<1e6;j+=j&-j) bit[j] += v; } int query(int j){ j++; int v = 0; for(;j;j-=j&-j) v += bit[j]; return v; } int query(int a, int b){ if(b < a) swap(a, b); return query(b) - query(a); } } F; long long count_swaps(std::vector<int> s) { int n = s.size(); vector<int> A[n + 1], B[n + 1]; for(int i = 0; i < n; i++){ if(s[i] < 0) A[-s[i]].push_back(i); else B[s[i]].push_back(i); } vector<pair<int, int> > Q; long long cnt = 0; for(int i = 0; i <= n; i++){ for(int j = 0; j < A[i].size(); j++){ if(B[i][j] < A[i][j]){ cnt++; swap(A[i][j], B[i][j]); } Q.push_back({A[i][j], B[i][j]}); } } sort(Q.begin(), Q.end(), [&](pair<int, int> a, pair<int, int> b){ return a.second < b.second; }); for(auto p : Q){ int l = p.first; int r = p.second; cnt += F.query(l, r); F.modify(l, 1); F.modify(r, 1); } return cnt; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int j = 0; j < A[i].size(); 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...