結果
問題 | No.2890 Chiffon |
ユーザー |
|
提出日時 | 2024-09-13 23:16:11 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,591 bytes |
コンパイル時間 | 2,390 ms |
コンパイル使用メモリ | 204,048 KB |
実行使用メモリ | 14,928 KB |
最終ジャッジ日時 | 2024-09-13 23:16:17 |
合計ジャッジ時間 | 4,865 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 WA * 2 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, n) for (int i = 0; i < (int)(n); i++)void solve() {ll n, k;cin >> n >> k;vector<ll> a(k);rep(i, k) cin >> a[i];{vector<ll> na(k);ll min_d = 1e18, min_i = -1;rep(i, k) {ll d = a[(i + 1) % k] - a[i];if (i == k - 1)d += n * 2;if (d < min_d) {min_d = d;min_i = i;}}ll x = a[min_i] - 1;rep(i, k) {ll j = (i + min_i) % k;na[i] = a[j] - x;if (j < min_i)na[i] += n * 2;}swap(a, na);}vector<ll> sum(n * 2 + 10, 0);{ll j = 0;rep(i, n * 2 + 5) {sum[i + 1] = sum[i];if (j < k && a[j] == i + 1) {sum[i + 1]++;j++;}}}ll ans = -1;for (ll s = 2; s < a[1]; s += 2) {ll L = 2, R = n * 2 / k + 2;while (L + 2 < R) {ll w = (L + R) / 2, now = s;bool ok = true;rep(i, k - 1) {ll nex = max(now + w, a[i + 1] + 1);if (nex > n * 2) {ok = false;break;}ok &= sum[nex] - sum[now] == 1;if (!ok)break;now = nex;}ok &= sum[n * 2 + 1] - sum[now] == 0;ok &= n * 2 - now + s >= w;if (ok) {L = w;} else {R = w;}}ans = max(ans, L);}if (ans % 2)ans--;cout << ans << '\n';}int main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);int T = 1;for (int t = 0; t < T; t++) {solve();}return 0;}