Submission #397797

#	Time	Username	Problem	Language	Result	Execution time	Memory
397797		qwerty234	Boxes with souvenirs (IOI15_boxes)	C++14	35 / 100	1 ms	460 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();
    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 {
    ll 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) {
    ll 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 {
      val_cw[-type] += x;
    }
  }
}

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();
    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 {
    ll 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) {
    ll 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 {
      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 <ll> p = {};
  for (ll 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(); //ll cnt0 = 0;
  for (ll 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<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 = s_ccw % k;
    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 = 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;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:139: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]
  139 |   for (ll i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~

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