結果
問題 | No.2890 Chiffon |
ユーザー | tottoripaper |
提出日時 | 2024-09-15 22:10:08 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,586 bytes |
コンパイル時間 | 2,315 ms |
コンパイル使用メモリ | 207,084 KB |
実行使用メモリ | 30,576 KB |
最終ジャッジ日時 | 2024-09-15 22:11:05 |
合計ジャッジ時間 | 27,647 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 TLE * 5 |
ソースコード
#include <bits/stdc++.h>using ll = std::int64_t;int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);ll N, K;std::cin >> N >> K;std::vector<int> A(2 * K);for(int i=0;i<K;i++){std::cin >> A[i];A[i + K] = A[i] + 2 * N;}auto mul = [](std::vector<int> a, std::vector<int> b){std::vector<int> res(a.size());for(int i=0;i<a.size();i++){res[i] = b[a[i]];}return res;};auto pow = [&mul](std::vector<int> a, int n){std::vector<int> res(a.size());std::iota(res.begin(), res.end(), 0);while(n > 0){if(n & 1){res = mul(res, a);}a = mul(a, a);n /= 2;}return res;};auto f = [&](int x){std::vector<int> B(2 * N + 1);B[2 * N] = 2 * N;for(int i=0;i<2*N;i++){int j = std::lower_bound(A.begin(), A.end(), 2 * i) - A.begin();if(j == A.size()){B[i] = 2 * N;}else{B[i] = std::min<int>(std::max((A[j] + 1) / 2, i + x), 2 * N);}}std::vector<int> C = pow(B, K);for(int i=0;i<N;i++){if(C[i] <= i + N){return true;}}return false;};int ok = 1, ng = N + 1;while(ng - ok > 1){int m = (ok + ng) / 2;if(f(m)){ok = m;}else{ng = m;}}int res = ok * 2;std::cout << res << std::endl;}