oj.uz

Submission #375285

# Submission time Handle Problem Language Result Execution time Memory
375285 2021-03-09T06:15:38 Z Mamnoon_Siam Swap (BOI16_swap) C++17
48 / 100
 199 ms 191724 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 2e3 + 3;

vi dp[N][N];
int a[N], n, nn;

vi merge(vi p, vi q) {
  vi r;
  int pw = 1;
  int i = 0, j = 0;
  while(i < sz(p) or j < sz(q)) {
    r.insert(r.end(), p.begin()+i, p.begin()+min(sz(p), i+pw));
    r.insert(r.end(), q.begin()+j, q.begin()+min(sz(q), j+pw));
    i = min(i+pw, sz(p));
    j = min(j+pw, sz(q));
    pw *= 2;
  }
  return r;
}

vi f(int u, int k) {
  if(sz(dp[u][k])) return dp[u][k];
  vi& ret = dp[u][k];
  if(2*u > nn) return ret = {k};
  { // don't use any edge
    vi l = f(2*u, a[2*u]);
    vi r = f(2*u+1, a[2*u+1]);
    ret = merge(l, r);
    ret.insert(ret.begin(), k);
  }
  { // use only left edge
    vi l = f(2*u, k);
    vi r = f(2*u+1, a[2*u+1]);
    vi tmp = merge(l, r);
    tmp.insert(tmp.begin(), a[2*u]);
    ret = min(ret, tmp);
  }
  { // use only right edge
    vi l = f(2*u, a[2*u]);
    vi r = f(2*u+1, k);
    vi tmp = merge(l, r);
    tmp.insert(tmp.begin(), a[2*u+1]);
    ret = min(ret, tmp);
  }
  { // use both edges
    vi l = f(2*u, k);
    vi r = f(2*u+1, a[2*u]);
    vi tmp = merge(l, r);
    tmp.insert(tmp.begin(), a[2*u+1]);
    ret = min(ret, tmp);
  }
  return ret;
}

int main(int argc, char* argv[]) {
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> n;
  nn = 1;
  while(nn-1 < n) nn *= 2;
  nn--;
  for(int i = 1; i <= n; ++i)
    cin >> a[i];
  for(int i = n+1; i <= nn; ++i)
    a[i] = n+1;
  vi ans = f(1, a[1]);
  for(int i = 0; i < n; ++i)
    cout << ans[i] << ' ';
  cout << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94572 KB Output is correct
2 Correct 67 ms 94572 KB Output is correct
3 Correct 68 ms 94572 KB Output is correct
4 Correct 65 ms 94572 KB Output is correct
5 Correct 64 ms 94572 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94572 KB Output is correct
2 Correct 67 ms 94572 KB Output is correct
3 Correct 68 ms 94572 KB Output is correct
4 Correct 65 ms 94572 KB Output is correct
5 Correct 64 ms 94572 KB Output is correct
6 Correct 66 ms 94572 KB Output is correct
7 Correct 72 ms 94700 KB Output is correct
8 Correct 65 ms 94572 KB Output is correct
9 Correct 66 ms 94572 KB Output is correct
10 Correct 66 ms 94572 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94572 KB Output is correct
2 Correct 67 ms 94572 KB Output is correct
3 Correct 68 ms 94572 KB Output is correct
4 Correct 65 ms 94572 KB Output is correct
5 Correct 64 ms 94572 KB Output is correct
6 Correct 66 ms 94572 KB Output is correct
7 Correct 72 ms 94700 KB Output is correct
8 Correct 65 ms 94572 KB Output is correct
9 Correct 66 ms 94572 KB Output is correct
10 Correct 66 ms 94572 KB Output is correct
11 Correct 76 ms 95212 KB Output is correct
12 Correct 80 ms 95212 KB Output is correct
13 Correct 77 ms 95212 KB Output is correct
14 Correct 76 ms 95212 KB Output is correct
15 Correct 75 ms 95340 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94572 KB Output is correct
2 Correct 67 ms 94572 KB Output is correct
3 Correct 68 ms 94572 KB Output is correct
4 Correct 65 ms 94572 KB Output is correct
5 Correct 64 ms 94572 KB Output is correct
6 Correct 66 ms 94572 KB Output is correct
7 Correct 72 ms 94700 KB Output is correct
8 Correct 65 ms 94572 KB Output is correct
9 Correct 66 ms 94572 KB Output is correct
10 Correct 66 ms 94572 KB Output is correct
11 Correct 76 ms 95212 KB Output is correct
12 Correct 80 ms 95212 KB Output is correct
13 Correct 77 ms 95212 KB Output is correct
14 Correct 76 ms 95212 KB Output is correct
15 Correct 75 ms 95340 KB Output is correct
16 Runtime error 199 ms 191724 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94572 KB Output is correct
2 Correct 67 ms 94572 KB Output is correct
3 Correct 68 ms 94572 KB Output is correct
4 Correct 65 ms 94572 KB Output is correct
5 Correct 64 ms 94572 KB Output is correct
6 Correct 66 ms 94572 KB Output is correct
7 Correct 72 ms 94700 KB Output is correct
8 Correct 65 ms 94572 KB Output is correct
9 Correct 66 ms 94572 KB Output is correct
10 Correct 66 ms 94572 KB Output is correct
11 Correct 76 ms 95212 KB Output is correct
12 Correct 80 ms 95212 KB Output is correct
13 Correct 77 ms 95212 KB Output is correct
14 Correct 76 ms 95212 KB Output is correct
15 Correct 75 ms 95340 KB Output is correct
16 Runtime error 199 ms 191724 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -