제출 #793150

#제출 시각아이디문제언어결과실행 시간메모리
793150RecursiveCo밀림 점프 (APIO21_jumps)C++14
23 / 100
1161 ms83520 KiB
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} //#define int long long vector<pair<int, int>> lpts; vector<pair<int, int>> rpts; vector<pair<int, int>> maxima; vector<vector<pair<int, int>>> greedylift; vector<vector<pair<int, int>>> rightlift; vector<int> arr; void init(int n, vector<int> nums) { lpts.resize(n); rpts.resize(n); maxima.resize(n); stack<pair<int, int>> st; forto(n, i) { while (!st.empty() && st.top().first < nums[i]) st.pop(); if (st.empty()) lpts[i] = {1e18, -1}; else lpts[i] = {st.top().first, st.top().second}; st.push({nums[i], i}); } while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && st.top().first < nums[i]) st.pop(); if (st.empty()) rpts[i] = {1e18, -1}; else rpts[i] = {st.top().first, st.top().second}; st.push({nums[i], i}); } forto(n, i) maxima[i] = max(lpts[i], rpts[i]); // Binary lifting. greedylift.resize(n, vector<pair<int, int>>(19, {1e18, -1})); rightlift.resize(n, vector<pair<int, int>>(19, {1e18, -1})); for (int i = n - 1; i >= 0; i--) { rightlift[i][0] = rpts[i]; for (int j = 1; j < 19; j++) { if (rightlift[i][j - 1].second == -1) break; rightlift[i][j] = rightlift[rightlift[i][j - 1].second][j - 1]; } } vector<pair<int, int>> sorted; forto(n, i) sorted.push_back({nums[i], i}); sortl(sorted); for (int ip = n - 1; ip >= 0; ip--) { int i = sorted[ip].second; greedylift[i][0] = maxima[i]; for (int j = 1; j < 19; j++) { if (greedylift[i][j - 1].second == -1) break; greedylift[i][j] = greedylift[greedylift[i][j - 1].second][j - 1]; } } forto(n, i) arr.push_back(nums[i]); } int minimum_jumps(int a, int b, int c, int d) { if (a != b || c != d) return -1; // this is a temporary thing since I'm only implementing A=B; C=D. int S = a; int T = c; int sheight = arr[S]; int theight = arr[T]; int steps = 0; int power = 1 << 18; int blift = 18; int index = S; while (blift >= 0) { auto dest = greedylift[index][blift]; if (dest.first <= theight && dest.second != -1) { steps += power; index = dest.second; } blift--; power /= 2; } power = 1 << 18; blift = 18; while (blift >= 0) { auto dest = rightlift[index][blift]; if (dest.first <= theight && dest.second != -1) { steps += power; index = dest.second; } blift--; power /= 2; } if (arr[index] == theight) return steps; else return -1; }

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:32:5: note: in expansion of macro 'forto'
   32 |     forto(n, i) {
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:45:5: note: in expansion of macro 'forto'
   45 |     forto(n, i) maxima[i] = max(lpts[i], rpts[i]);
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:57:5: note: in expansion of macro 'forto'
   57 |     forto(n, i) sorted.push_back({nums[i], i});
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:68:5: note: in expansion of macro 'forto'
   68 |     forto(n, i) arr.push_back(nums[i]);
      |     ^~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:75:9: warning: unused variable 'sheight' [-Wunused-variable]
   75 |     int sheight = arr[S];
      |         ^~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...