제출 #143575

#제출 시각아이디문제언어결과실행 시간메모리
143575abekerArranging Shoes (IOI19_shoes)C++17
100 / 100
99 ms19192 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 5; int N; vector <int> lft[MAXN], rig[MAXN]; int fen[MAXN]; void update(int x) { for (x++; x < MAXN; x += x & -x) fen[x]++; } int get(int x) { int res = 0; for (x++; x; x -= x & -x) res += fen[x]; return res; } ll count_swaps(vector <int> shoes) { N = shoes.size(); vector <int> todo(N, -1); for (int i = 0; i < N; i++) { int sz = abs(shoes[i]); if (shoes[i] < 0) lft[sz].push_back(i); else rig[sz].push_back(i); } ll sol = 0; for (int i = 1; i <= N / 2; i++) for (int j = 0; j < lft[i].size(); j++) { if (lft[i][j] > rig[i][j]) { swap(lft[i][j], rig[i][j]); sol++; } todo[rig[i][j]] = lft[i][j]; } for (int i = 0; i < N; i++) if (todo[i] != -1) { sol += get(N) - get(todo[i]); update(todo[i]); update(i); } return sol; }

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

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lft[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...