Submission #397812

#	Time	Username	Problem	Language	Result	Execution time	Memory
397812		qwerty234	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	15 ms	332 KiB

boxes

#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 <ll> val_cw, val_ccw, cf_cw, cf_ccw;
vector <pair<ll, ll>> op_cw, op_ccw, cw, ccw;;
ll 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(ll x, bool flag) {
  if (s_cw == 0) {
    op_cw.clear();
    return;
  }
  if (flag) {
    ll i = n_cw - 1; op_cw.clear();
    op_cw.pb({1, ans_cw});
    op_cw.pb({2, s_cw});
    while (x > 0 && i >= 0) {
      while (x > 0 && cw[i].se > 0) {
        cw[i].se--; x--; op_cw.pb({3, i});
      }
      i--;
    }
    ans_cw = 0; s_cw = 0;
    for (ll 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];
    }
  } else {
    ll i = n_cw - 1;
    while (cw[i].se == 0)
      i--;
    add_cw += (ll)cw[i].fi;
    while (x > 0 && i >= 0) {
      while (x > 0 && cw[i].se > 0) {
        cw[i].se--; x--;
      }
      i--;
    }
    ans_cw = 0; s_cw = 0;
    for (ll 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];
    }
  }
}

void roll_back_cw() {
  while (op_cw.size() != 0) {
    ll type = op_cw[op_cw.size() - 1].fi, x = op_cw[op_cw.size() - 1].se;
    op_cw.pop_back();
    if (type == 1) {
      ans_cw = x;
    } else if (type == 2) {
      s_cw = x;
    } else if (type == 3) {
      cw[x].se++;
    }
  }
}

void process_ccw(ll x, bool flag) {
  if (s_ccw == 0) {
    op_ccw.clear();
    return;
  }
  if (flag) {
    ll i = n_ccw - 1; op_ccw.clear();
    op_ccw.pb({1, ans_ccw});
    op_ccw.pb({2, s_ccw});
    while (x > 0 && i >= 0) {
      while (x > 0 && cw[i].se > 0) {
        ccw[i].se--; x--; op_ccw.pb({3, i});
      }
      i--;
    }
    ans_ccw = 0; s_ccw = 0;
    for (ll 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];
    }
  } else {
    ll i = n_ccw - 1;
    while (ccw[i].se == 0)
      i--;
    add_ccw += (ll)l - (ll)ccw[i].fi;
    while (x > 0 && i >= 0) {
      while (x > 0 && ccw[i].se > 0) {
        ccw[i].se--; x--;
      }
      i--;
    }
    ans_ccw = 0; s_ccw = 0;
    for (ll 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];
    }
  }
}

void roll_back_ccw() {
  while (op_ccw.size() != 0) {
    ll type = op_ccw[op_ccw.size() - 1].fi, x = op_ccw[op_ccw.size() - 1].se;
    op_ccw.pop_back();
    if (type == 1) {
      ans_ccw = x;
    } else if (type == 2) {
      s_ccw = x;
    } else if (type == 3) {
      ccw[x].se++;
    }
  }
}

// ll delivery(int n1, int k1, int l1, vector <ll> p) {
ll delivery(int n1, int k1, int l1, int p1[]) {
  vector <ll> p = {};
  for (ll i = 0; i < n1; i++)
    p.pb(p1[i]);
  n = n1; k = k1; l = l1;
  if (n > 3010 || k > 3010)
    return 0;
  sort(p.begin(), p.end());
  add = 0;
  cw.clear(); ccw.clear(); ll cnt0 = 0;
  for (ll i = 0; i < p.size(); i++) {
    if (p[i] == 0)
      cnt0++;
    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<ll, ll> to : cw)
  //   cout << to.fi << " " << to.se << endl;
  // cout << endl;
  // for (pair<ll, ll> 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 (ll 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 (ll 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 (ll 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 (ll 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; ll cur = 0;
  while (true) {
    // cur++;
    ll cnt, mod; ll tmp;
    cnt = (s_ccw + add + k - 1) / k; mod = k * cnt - (s_ccw + add);
    tmp = (ll)cnt * (ll)l;
    // cout << cur << " " << cnt << " " << tmp << " " << mod << endl;
    process_cw(mod, true);
    // if (ans_cw < 0 || add_cw < 0 || ans_ccw < 0 || add_ccw < 0)
    //   return -1;
    // 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 = k * cnt - (s_cw + add);
    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 << " " << s_cw << " " << s_ccw << endl;
    ans = min(ans, tmp + 2ll * (add_cw + add_ccw));
    if (s_cw == 0 && s_ccw == 0)
      break;
  }
  return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'void process_cw(long long int, bool)':
boxes.cpp:30:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   30 |     for (ll i = n_cw - 1; i >= 0; i--) {
      |             ^
boxes.cpp:20:8: note: shadowed declaration is here
   20 |     ll i = n_cw - 1; op_cw.clear();
      |        ^
boxes.cpp:47:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   47 |     for (ll i = n_cw - 1; i >= 0; i--) {
      |             ^
boxes.cpp:36:8: note: shadowed declaration is here
   36 |     ll i = n_cw - 1;
      |        ^
boxes.cpp: In function 'void process_ccw(long long int, bool)':
boxes.cpp:85:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   85 |     for (ll i = n_ccw - 1; i >= 0; i--) {
      |             ^
boxes.cpp:75:8: note: shadowed declaration is here
   75 |     ll i = n_ccw - 1; op_ccw.clear();
      |        ^
boxes.cpp:102:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
  102 |     for (ll i = n_ccw - 1; i >= 0; i--) {
      |             ^
boxes.cpp:91:8: note: shadowed declaration is here
   91 |     ll i = n_ccw - 1;
      |        ^
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:135:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for (ll i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30