제출 #893004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893004		d4xn	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	35627 ms	262148 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

const int N = 1e6+6;

int n, k, a[N], p[N], sz[N], val[N], lp[N], rp[N], z[N];
vector<int> add[N];
set<pair<int, int>> edges;

int findSet(int i) {
  if (p[i] == i) return i;
  return p[i] = findSet(p[i]);
}

void unite(int i, int j) {
  i = findSet(i);
  j = findSet(j);

  assert(val[i] == val[j]);
  if (sz[i] < sz[j]) swap(i, j);

  p[j] = i;
  sz[i] += sz[j];
  val[i]++;
  lp[i] = min(lp[i], lp[j]);
  rp[i] = max(rp[i], rp[j]);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];

    p[i] = i;
    sz[i] = 1;
    val[i] = a[i];
    lp[i] = i;
    rp[i] = i;

    z[i] = 0;
  }

  for (int i = 0; i+1 < n; i++) {
    edges.insert(make_pair(abs(a[i]-a[i+1]), i));
  }

  while (!edges.empty()) {
    auto it = edges.begin();
    int sk = it->first;
    int l = it->second;
    edges.erase(it);

    int x = findSet(l);
    int y = findSet(l+1);
    if (x == y) continue;

    if (val[x] != val[y]) {
      if (val[x] < val[y]) {
        for (int i = val[x]; i < val[y]; i++) {
          add[l].push_back(i);
          k--;
        }
        val[x] = val[y];
      }
      else {
        for (int i = val[x]-1; i >= val[y]; i--) {
          add[l].push_back(i);
          k--;
        }
        val[y] = val[x];
      }
    }

    unite(x, y);

    int nwP = findSet(x);
    int nwLp = lp[nwP];
    int nwRp = rp[nwP];

    if (nwLp) edges.insert(make_pair(abs(val[findSet(nwLp-1)] - val[nwP]), nwLp-1));
    if (nwRp+1 < n) edges.insert(make_pair(abs(val[nwP] - val[findSet(nwRp+1)]), nwRp));
  }

  assert(k >= 0);
  int mx = val[findSet(0)];
  for (int i = 0; i < n; i++) {
    while (!add[i].empty() && k > 0) {
      int x = add[i].back();
      if (!x) {
        add[i].pop_back();
        z[i]++;
      }
      else {
        add[i].pop_back();
        add[i].push_back(x-1);
        add[i].push_back(x-1);
        k--;
      }
    }

    if (i == n-1 && k > 0) {
      add[i].push_back(mx++);
      k--;
      i--;
    }
  }
  assert(!k);

  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
    for (int& j : add[i]) cout << j << " ";
    while (z[i]) {
      cout << "0 ";
      z[i]--;
    }
  }
  cout << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:54:9: warning: unused variable 'sk' [-Wunused-variable]
   54 |     int sk = it->first;
      |         ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70