제출 #1012995

#제출 시각아이디문제언어결과실행 시간메모리
1012995aufanArranging Shoes (IOI19_shoes)C++17
100 / 100
174 ms27624 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long count_swaps(vector<int> s) { int n = s.size(); long long ans = 0; int p = 0; vector<int> fin(n); map<int, vector<int>> id; for (int i = 0; i < n; i++) { id[s[i]].push_back(i); } vector<pair<int, int>> br; for (int i = 1; i <= n/2; i++) { int sz = id[i].size(); for (int j = 0; j < sz; j++) { int lf = min(id[-i][j], id[i][j]); int rg = max(id[-i][j], id[i][j]); br.push_back(make_pair(lf, rg)); } } /* 1 1 -1 -1 0 1 2 3 {0, 2}, {1, 3} */ sort(br.begin(), br.end()); for (int i = 0; i < n/2; i++) { fin[2*i] = br[i].first; fin[2*i + 1] = br[i].second; if (s[fin[2*i]] > 0) swap(fin[2*i], fin[2*i + 1]); } /* 0 1 2 3 4 5 0 2 1 4 3 5 0 2 1 4 5 3 */ vector<int> fen(n+1, 0); auto add = [&](int x) { for (;x<=n;x+=x&-x) fen[x]++; }; auto get = [&](int x) { int res = 0; for (;x>0;x-=x&-x) res+=fen[x]; return res; }; for (int i = 0; i < n; i++) { int pos = fin[i] + 1 + (get(n) - get(fin[i]+1)); ans += pos - i - 1; add(fin[i]+1); } return ans; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:9:9: warning: unused variable 'p' [-Wunused-variable]
    9 |     int p = 0;
      |         ^
#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...