제출 #1209120

#제출 시각아이디문제언어결과실행 시간메모리
1209120jer033고대 책들 (IOI17_books)C++20
50 / 100
97 ms10428 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); ll base_cost = 0; for (int i=0; i<n; i++) base_cost += abs(p[i]-i); vector<pii> cycles; vector<bool> used(n, 0); for (int i=0; i<n; i++) if (used[i]==0) { used[i]=1; int mini = i; int maxi = i; int curr = p[i]; while (curr!=i) { used[curr] = 1; maxi = max(curr, maxi); curr = p[curr]; } if (mini!=maxi) cycles.push_back({mini, maxi}); } int k = cycles.size(); ll penalty = 0; int curr_max = -1; for (int i=0; i<k; i++) { if (i==0) penalty = cycles[0].first; else if (cycles[i].first > curr_max) penalty += cycles[i].first - curr_max; curr_max = max(curr_max, cycles[i].second); } return base_cost + 2ll*penalty; }
#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...