結果
問題 | No.2890 Chiffon |
ユーザー |
![]() |
提出日時 | 2024-09-14 01:02:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,959 bytes |
コンパイル時間 | 4,557 ms |
コンパイル使用メモリ | 275,448 KB |
実行使用メモリ | 338,480 KB |
最終ジャッジ日時 | 2024-09-14 01:03:28 |
合計ジャッジ時間 | 26,540 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 TLE * 1 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0; i < (int)n; i++)#define FOR(n) for(int i = 0; i < (int)n; i++)#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)#define all(x) x.begin(),x.end()//#define mp make_pair#define vi vector<int>#define vvi vector<vi>#define vvvi vector<vvi>#define vvvvi vector<vvvi>#define pii pair<int,int>#define vpii vector<pair<int,int>>template<typename T>bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}}template<typename T>bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}}using ll = long long;using ld = long double;using ull = unsigned long long;const ll INF = numeric_limits<long long>::max() / 2;const ld pi = 3.1415926535897932384626433832795028;const ll mod = 998244353;int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};#define int long longvoid solve() {int n, k;cin >> n >> k;vi a(k);FOR(k) cin >> a[i];int obvious_upper = 2 * n/ k;vector<bool> strawberry(2*n, false);FOR(k) {strawberry[a[i]] = true;if(k > 2) chmin(obvious_upper, abs(a[i] - a[(i+2)%k]));}auto cal_dist = [n](int from, int to) -> int {if(from < to) return to - from;return 2*n - from + to;};vi bits;FOR(20) if(k>>i&1) bits.emplace_back(i);int l = 0, r = obvious_upper+1;while(r-l > 1) {int mid = (l + r) / 2;vi to(2*n, -1);int cur_r = 0;int strawberry_cnt = 0;for(int i = 0; i < 2*n; i += 2) {while(strawberry_cnt == 0 || cur_r-i < mid) {if(strawberry[(cur_r+1) % (2*n)]) ++strawberry_cnt;cur_r += 2;}to[i] = cur_r % (2 * n);if(strawberry[(i + 1) % (2*n)]) --strawberry_cnt;}vvi distd(20, vi(2*n, -1)), tod(20, vi(2*n, -1));for(int i = 0; i < 2*n; i += 2) distd[0][i] = cal_dist(i, to[i]);tod[0] = to;rep(lg, 19) for(int i = 0; i < 2*n; i += 2) {tod[lg+1][i] = tod[lg][tod[lg][i]];distd[lg+1][i] = distd[lg][i] + distd[lg][tod[lg][i]];}// cerr << mid << endl;// FOR(2*n) cout << to[i] << " \n"[i == 2*n-1];bool can_cut = false;for(int i = 0; i < 2*n; i += 2) {int cur_place = i, dist = 0;for(int &bit : bits) {dist += distd[bit][cur_place];cur_place = tod[bit][cur_place];}if(dist <= 2 * n) {can_cut = true;break;}}if(can_cut) l = mid;else r = mid;}cout << l << endl;}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}