제출 #1195763

#제출 시각아이디문제언어결과실행 시간메모리
1195763madamadam3선물상자 (IOI15_boxes)C++20
0 / 100
1613 ms408 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = a; i < b; i++) #define pb push_back #define all(x) (x).begin(), (x).end() #define srt(x) sort(all(x)) typedef long long ll; using vi = vector<int>; using vl = vector<ll>; // probably binary search? ll n, k, l; vl p; vl nxt, prev; ll sim_dist(ll p1, ll p2) { ll lmoves = 0, rmoves = 0; ll lpos = p1, rpos = p1; while (lpos != p2) { lpos--; if (lpos < 0) lpos = l - 1; lmoves++; } while (rpos != p2) { rpos++; if (rpos >= l) rpos = 0; rmoves++; } return min(lmoves, rmoves); } ll dist(ll p1, ll p2) { if (p1 == p2) return 0; if (p1 < p2) return dist(p2, p1); else return min(p1 - p2, (l - p1) + p2); } // going left for kL teams and coming back ll sim_left(ll kL) { ll ansL = 0, pL = 0; FOR(i, 0, kL) { ll pidx = n - ll(i) - 1; if (pL == 0) ansL += l - p[pidx]; else ansL += pL - p[pidx]; pL = p[pidx]; } ansL += sim_dist(pL, 0); return ansL; } // going right for kR teams and coming back ll sim_right(ll kR) { ll ansR = 0, pR = 0; FOR(i, 0, kR) { ll pidx = 0 + i; ansR += p[pidx] - pR; pR = p[pidx]; } ansR += sim_dist(pR, 0); return ansR; } ll delivery(int N, int K, int L, int P[]) { n = N, k = K, l = L; FOR(i, 0, n) p.pb(P[i]); srt(p); ll lo = 0, hi = n; while (lo < hi) { ll mid = lo + (hi - lo) / 2; ll kL = mid, kR = n - mid; ll ans = sim_left(kL) + sim_right(kR); ll ans2 = sim_left(kL + 1) + sim_right(kR - 1); if (ans < ans2) { hi = mid; } else { lo = mid + 1; } } return sim_left(lo) + sim_right(lo); // return min(*max_element(all(p)) + dist(*max_element(all(p)), 0), l - *min_element(all(p)) + dist(*min_element(all(p)), 0)); // ll max_pos = *max_element(all(p)); // ll min_pos = *min_element(all(p)); // ll min_dist = dist(min_pos, l); // return min({l, 2LL * max_pos, 2LL * min_dist}); }
#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...