oj.uz

Submission #893004

# Submission time Handle Problem Language Result Execution time Memory
893004 2023-12-26T10:05:05 Z d4xn Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 262148 KB 
#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";
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 237528 KB Time limit exceeded
2 Execution timed out 3047 ms 262144 KB Time limit exceeded
3 Execution timed out 33941 ms 262148 KB Time limit exceeded
4 Execution timed out 3281 ms 262144 KB Time limit exceeded
5 Execution timed out 32128 ms 262144 KB Time limit exceeded
6 Execution timed out 35627 ms 262144 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 35548 ms 262144 KB Time limit exceeded
2 Execution timed out 1080 ms 262144 KB Time limit exceeded
3 Execution timed out 1034 ms 262144 KB Time limit exceeded
4 Execution timed out 33195 ms 262144 KB Time limit exceeded
5 Execution timed out 35571 ms 262144 KB Time limit exceeded
6 Execution timed out 35565 ms 262144 KB Time limit exceeded
7 Execution timed out 35571 ms 262144 KB Time limit exceeded
8 Execution timed out 30569 ms 262144 KB Time limit exceeded
9 Execution timed out 2948 ms 262144 KB Time limit exceeded
10 Runtime error 348 ms 176464 KB Execution killed with signal 6
11 Runtime error 550 ms 246488 KB Execution killed with signal 6
12 Incorrect 28 ms 39348 KB not a zalsequence
13 Incorrect 28 ms 39508 KB not a zalsequence
14 Incorrect 30 ms 39516 KB not a zalsequence