QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351780#8225. 最小值之和JCY_0 2ms5756kbC++143.9kb2024-03-12 14:54:192024-03-12 14:54:19

Judging History

你现在查看的是最新测评结果

  • [2024-03-12 14:54:19]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5756kb
  • [2024-03-12 14:54:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
int ceil_div(int x, int y) { return x <= 0 ? x / y : (x - 1) / y + 1; }
int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
constexpr int MAXN = 82;
int n, a[MAXN], f[MAXN][MAXN][MAXN], temp[MAXN], ans[MAXN];
void print(int l, int r, int v) {
  if (l == r) return;
  int x, y = 0;
  for (x = l; x < r; ++x) {
    if (x == l && x + 1 == r) {
      if (a[l] == a[r] && (a[l] - v) % (r - l) == 0) {
        y = (a[l] - v) / (r - l);
        break;
      }
    } else if (x == l) {
      if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l] && (a[l] - v) % (r - l) == 0) {
        y = (a[l] - v) / (r - l);
        break;
      }
    } else if (x + 1 == r) {
      if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r] && (a[r] - v) % (r - l) == 0) {
        y = (a[r] - v) / (r - l);
        break;
      }
    } else {
      int up = (x - l) / __gcd(x - l, r - x - 1) * (r - x - 1);
      for (y = 0; y < up; ++y) {
        if (f[l][x][(v + y * (r - l)) % (x - l)] >= v + y * (r - l) && 
            f[x + 1][r][(v + y * (r - l)) % (r - x - 1)] >= v + y * (r - l)) {
          break;
        }
      }
      if (y != up) break;
    }
  }
  assert(x != r);
  print(l, x, v + y * (r - l));
  print(x + 1, r, v + y * (r - l));
  for (int i = l; i < r; ++i) ans[i] += y;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  if (n == 1) {
    cout << (a[1] ? "No" : "Yes\n") << "\n";
    return 0;
  }
  memset(f, -1, sizeof(f));
  for (int l = n; l >= 1; --l) {
    for (int r = l + 1; r <= n; ++r) {
      for (int x = l; x < r; ++x) {
        if (x == l && x + 1 == r) {
          if (a[l] == a[r]) chkmax(f[l][r][a[l] % (r - l)], a[l]);
        } else if (x == l) {
          if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l])
            chkmax(f[l][r][a[l] % (r - l)], a[l]);
        } else if (x + 1 == r) {
          if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r])
            chkmax(f[l][r][a[r] % (r - l - 1)], a[r]);
        } else {
          fill(temp, temp + r - l, -1);
          int sx, sy, d = exgcd(x - l, r - x - 1, sx, sy);
          sy = -sy;
          int coef = max(ceil_div(-sx, (r - x - 1) / d), ceil_div(-sy, (x - l) / d));
          sx += (r - x - 1) / d * coef;
          sy += (x - l) / d * coef;
          for (int i = 0; i < x - l; ++i) {
            if (f[l][x][i] == -1) continue;
            for (int j = 0; j < r - x - 1; ++j) {
              if (f[x + 1][r][j] == -1) continue;
              int c = f[l][x][i] - f[x + 1][r][j];
              if (c % d) continue;
              ll fst = f[l][x][i] - (ll)c / d * sx * (x - l);
              if (fst >= 0) chkmax(temp[fst % (r - l)], (int)fst);
            }
          }
          d = (x - l) / d * (r - x - 1);
          for (int s = 0, td = d % (r - l), up = __gcd(r - l, td); s < up; ++s) {
            auto nxt = [&](int v) {
              v -= td;
              return v < 0 ? v + r - l : v;
            };
            for (int turn = 0; turn < 2; ++turn) {
              for (int i = s, j = nxt(s);; i = j, j = nxt(j)) {
                chkmax(temp[j], temp[i] - d);
                if (j == s) break;
              }
            }
          }
        }
      }
    }
  }
  if (f[1][n][0] == -1) {
    cout << "No\n";
    return 0;
  }
  cout << "Yes\n";
  print(1, n, 0);
  for (int i = 1; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
  return 0;
}
/*
g++ B.cpp -o B -std=c++14 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 5756kb

input:

5
14 14 12 13 13

output:

No

result:

wrong answer Line 1 expected 

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%