Submission #1195757

#TimeUsernameProblemLanguageResultExecution timeMemory
1195757madamadam3Boxes with souvenirs (IOI15_boxes)C++20
0 / 100
2097 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(int kL, deque<int> &cur) { ll ansL = 0, pL = 0; FOR(i, 0, kL) { if (pL == 0) ansL += l - cur.back(); else ansL += pL - cur.back(); pL = cur.back(); cur.pop_back(); } ansL += sim_dist(pL, 0); return ansL; } // going right for kR teams and coming back ll sim_right(int kR, deque<int> &cur) { ll ansR = 0, pR = 0; FOR(i, 0, kR) { ansR += cur.front() - pR; pR = cur.front(); cur.pop_front(); } 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); vl answers; FOR(i, 0, n+1) { int kL = i, kR = n - i; deque<int> cur = deque<int>(all(p)); answers.pb(sim_left(kL, cur) + sim_right(kR, cur)); } return *min_element(all(answers)); // 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...