| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 397790 | qwerty234 | Boxes with souvenirs (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
vector <int> val_cw, val_ccw, cf_cw, cf_ccw;
vector <pair<int, int>> op_cw, op_ccw, cw, ccw;;
int s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
ll ans_cw, ans_ccw, ans, add_cw, add_ccw, l;
void process_cw(int x, bool flag) {
if (s_cw == 0) {
op_cw.clear();
return;
}
if (flag) {
int i = n_cw - 1; op_cw.clear();
while (x > 0 && i >= 0) {
while (x > 0 && cw[i].se > 0) {
cw[i].se--; x--; op_cw.pb({1, i});
s_cw--; op_cw.pb({2, 0});
shift_cw = (shift_cw + 1) % k; op_cw.pb({3, 0});
ans_cw -= (ll)val_cw[shift_cw]; op_cw.pb({4, val_cw[shift_cw]});
}
if (cw[i].se == 0) {
n_cw--; op_cw.pb({5, 0});
val_cw[shift_cw] -= cf_cw[i]; op_cw.pb({-shift_cw, cf_cw[i]});
}
i--;
}
} else {
int i = n_cw - 1; add_cw += (ll)cw[i].fi;
while (x > 0 && i >= 0) {
while (x > 0 && cw[i].se > 0) {
cw[i].se--; x--;
s_cw--;
shift_cw = (shift_cw + 1) % k;
ans_cw -= (ll)val_cw[shift_cw];
}
if (cw[i].se == 0) {
n_cw--;
val_cw[shift_cw] -= cf_cw[i];// op_cw.pb({-shift_cw, cf_cw[i]});
}
i--;
}
}
}
void roll_back_cw() {
while (op_cw.size() != 0) {
int type = op_cw[op_cw.size() - 1].fi, x = op_cw[op_cw.size() - 1].se;
op_cw.pop_back();
if (type == 1) {
cw[x].se++;
} else if (type == 2) {
s_cw++;
} else if (type == 3) {
shift_cw = (shift_cw + k - 1) % k;
} else if (type == 4) {
ans_cw += (ll)x;
} else if (type == 5) {
n_cw++;
} else if (type < 0) {
val_cw[-type] += x;
}
}
}
void process_ccw(int x, bool flag) {
if (s_ccw == 0) {
op_ccw.clear();
return;
}
if (flag) {
int i = n_ccw - 1; op_ccw.clear();
while (x > 0 && i >= 0) {
while (x > 0 && ccw[i].se > 0) {
ccw[i].se--; x--; op_ccw.pb({1, i});
s_ccw--; op_ccw.pb({2, 0});
shift_ccw = (shift_ccw + 1) % k; op_ccw.pb({3, 0});
ans_ccw -= (ll)val_ccw[shift_ccw]; op_ccw.pb({4, val_ccw[shift_ccw]});
}
if (ccw[i].se == 0) {
n_ccw--; op_ccw.pb({5, 0});
val_ccw[shift_ccw] -= cf_ccw[i]; op_ccw.pb({-shift_ccw, cf_ccw[i]});
}
i--;
}
} else {
int i = n_ccw - 1; add_ccw += (ll)(l - ccw[i].fi);
while (x > 0 && i >= 0) {
while (x > 0 && ccw[i].se > 0) {
ccw[i].se--; x--;
s_ccw--;
shift_ccw = (shift_ccw + 1) % k;
ans_ccw -= (ll)val_ccw[shift_ccw];
}
if (ccw[i].se == 0) {
n_ccw--;
val_ccw[shift_ccw] -= cf_ccw[i];// op_ccw.pb({-shift_ccw, cf_ccw[i]});
}
i--;
}
}
}
void roll_back_ccw() {
while (op_ccw.size() != 0) {
int type = op_ccw[op_ccw.size() - 1].fi, x = op_ccw[op_ccw.size() - 1].se;
op_ccw.pop_back();
if (type == 1) {
ccw[x].se++;
} else if (type == 2) {
s_ccw++;
} else if (type == 3) {
shift_ccw = (shift_ccw + k - 1) % k;
} else if (type == 4) {
ans_ccw += (ll)x;
} else if (type == 5) {
n_ccw++;
} else if (type < 0) {
val_ccw[-type] += x;
}
}
}
ll delivery(int n1, int k1, int l1, vector <ll> p) {
// ll delivery(int n1, int k1, int l1, int p1[]) {
// vector <int> p = {};
// for (int i = 0; i < n1; i++)
// p.pb(p1[i]);
n = n1; k = k1; l = l1;
sort(p.begin(), p.end());
add = 0;
cw.clear(); ccw.clear(); //int cnt0 = 0;
for (int i = 0; i < p.size(); i++) {
if (l % 2 == 0 && p[i] == l / 2) {
add++;
} else if (p[i] <= l / 2 && p[i] != 0) {
if (cw.size() == 0 || cw[cw.size() - 1].fi != p[i])
cw.pb({p[i], 0});
cw[cw.size() - 1].se++;
} else if (p[i] != 0) {
if (ccw.size() == 0 || ccw[ccw.size() - 1].fi != p[i])
ccw.pb({p[i], 0});
ccw[ccw.size() - 1].se++;
}
}
// n -= cnt0;
// for (pair<int, int> to : cw)
// cout << to.fi << " " << to.se << endl;
// cout << endl;
// for (pair<int, int> to : ccw)
// cout << to.fi << " " << to.se << endl;
reverse(ccw.begin(), ccw.end());
val_cw.assign(k, 0);
val_ccw.assign(k, 0);
n_cw = cw.size();
n_ccw = ccw.size();
cf_cw.assign(n_cw, 0);
for (int i = 0; i < n_cw; i++) {
if (i == 0)
cf_cw[i] = cw[i].fi;
else
cf_cw[i] = cw[i].fi - cw[i - 1].fi;
}
cf_ccw.assign(n_ccw, 0);
for (int i = 0; i < n_ccw; i++) {
if (i == 0)
cf_ccw[i] = l - ccw[i].fi;
else
cf_ccw[i] = ccw[i - 1].fi - ccw[i].fi;
}
// cout << "ok" << endl;
// return 0;
ans_cw = ans_ccw = s_cw = s_ccw = shift_cw = shift_ccw = add_cw = add_ccw = 0;
for (int i = n_cw - 1; i >= 0; i--) {
s_cw += cw[i].se;
val_cw[s_cw % k] += cf_cw[i];
ans_cw += (ll)((s_cw + k - 1) / k) * (ll)cf_cw[i];
}
for (int i = n_ccw - 1; i >= 0; i--) {
s_ccw += ccw[i].se;
val_ccw[s_ccw % k] += cf_ccw[i];
ans_ccw += (ll)((s_ccw + k - 1) / k) * (ll)cf_ccw[i];
}
// cout << ans_cw << " " << ans_ccw << endl;
// return 0;
ans = (ll)((n + k - 1) / k) * (ll)l;
// cout << ans << endl; int cur = 0;
while (true) {
// cur++;
int cnt, mod; ll tmp;
cnt = (s_ccw + add + k - 1) / k; mod = s_ccw % k;
tmp = (ll)cnt * (ll)l;
// cout << cur << " " << cnt << " " << tmp << " " << mod << endl;
process_cw(mod, true);
// cout << cur << " " << ans_cw << " " << add_cw << " " << tmp + 2ll * (ans_cw + add_cw) << endl;
ans = min(ans, tmp + 2ll * (ans_cw + add_cw + add_ccw));
roll_back_cw();
// cout << cur << " " << ans_cw << " " << s_cw << endl;
cnt = (s_cw + add + k - 1) / k; mod = s_cw % k;
tmp = (ll)cnt * (ll)l;
// cout << cur << " " << cnt << " " << tmp << " " << mod << endl;
process_ccw(mod, true);
// cout << cur << " " << ans_ccw << " " << add_ccw << " " << tmp + 2ll * (ans_ccw + add_ccw) << endl;
ans = min(ans, tmp + 2ll * (ans_ccw + add_ccw + add_cw));
roll_back_ccw();
// cout << cur << " " << ans_ccw << endl;
process_cw(k, false);
process_ccw(k, false);
cnt = (s_cw + s_ccw + add + k - 1) / k;
tmp = (ll)cnt * (ll)l;
// cout << "Dfsdf " << tmp << " " << add_cw << " " << add_ccw << endl;
ans = min(ans, tmp + 2ll * (add_cw + add_ccw));
if (s_cw == 0 && s_ccw == 0)
break;
}
return ans;
}