結果

問題 No.2890 Chiffon
ユーザー haihamabossuhaihamabossu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0