제출 #1010967

#제출 시각아이디문제언어결과실행 시간메모리
1010967alex_2008Arranging Shoes (IOI19_shoes)C++14
50 / 100
146 ms4956 KiB
#include "shoes.h" //#include "fish.h" #include <iostream> #include <cmath> #include <vector> #include <set> #include <map> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int N = 1e5 + 10, M = 110; bool used[N]; int fenwick[N]; void update(int ind, int diff, int n) { while (ind <= n) { fenwick[ind] += diff; ind += (ind & (-ind)); } } int sm(int ind) { int ans = 0; while (ind > 0) { ans += fenwick[ind]; ind -= (ind & (-ind)); } return ans; } ll count_swaps(vector<int> S) { int n = (int)S.size() / 2; if (n <= 1000) { ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 2 * n; j++) { //cout << S[j] << " "; } //cout << "\n"; map <int, int> mp; for (int j = 2 * i; j < 2 * n; j++) { if (mp.find(S[j]) == mp.end()) { mp[S[j]] = j; } } pair <int, int> esim = make_pair(-1, -1); int cur = 2 * n + 10; for (auto it : mp) { //cout << "? " << it.first << "\n"; if (it.first > 0) break; int x = it.second; int y = mp[-it.first]; int f = 0; if (x < y) { f = x + y - 4 * i - 1; } else { f = x + y - 4 * i; } if (f < cur) { cur = f; esim = make_pair(x, y); } } //cout << esim.first << " " << esim.second << "\n"; //cout << "#" << cur << "\n"; for (int j = esim.first; j > 2 * i; j--) { swap(S[j], S[j - 1]); } for (int j = esim.second + (esim.first > esim.second); j > 2 * i + 1; j--) { swap(S[j], S[j - 1]); } ans += cur; } return ans; } bool ch = true; for (auto& it : S) { if (abs(it) != abs(S[0])) ch = false; } if (ch) { //cout << "?\n"; vector <int> a; vector <int> b; for (int i = 0; i < 2 * n; i++) { if (S[i] < 0) a.push_back(i + 1); else b.push_back(i + 1); update(i + 1, 1, 2 * n); } ll ans = 0; for (int i = 0; i < n; i++) { ans += sm(a[i] - 1); update(a[i], -1, 2 * n); ans += sm(b[i] - 1); update(b[i], -1, 2 * n); } return ans; } } /* int main() { cout << count_swaps({ 2, 1, -1, -2 }) << "\n"; } */

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

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^
#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...