結果

問題 No.2890 Chiffon
ユーザー tonegawatonegawa
提出日時 2024-09-13 22:28:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 555 ms / 2,000 ms
コード長 6,699 bytes
コンパイル時間 1,530 ms
コンパイル使用メモリ 143,932 KB
実行使用メモリ 110,836 KB
最終ジャッジ日時 2024-09-26 14:41:09
合計ジャッジ時間 11,275 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 409 ms
98,176 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 138 ms
110,836 KB
testcase_24 AC 282 ms
58,496 KB
testcase_25 AC 220 ms
46,848 KB
testcase_26 AC 432 ms
89,088 KB
testcase_27 AC 508 ms
94,464 KB
testcase_28 AC 14 ms
7,168 KB
testcase_29 AC 37 ms
12,928 KB
testcase_30 AC 242 ms
51,456 KB
testcase_31 AC 494 ms
101,376 KB
testcase_32 AC 473 ms
88,832 KB
testcase_33 AC 18 ms
8,832 KB
testcase_34 AC 193 ms
107,132 KB
testcase_35 AC 192 ms
107,128 KB
testcase_36 AC 191 ms
107,260 KB
testcase_37 AC 191 ms
107,260 KB
testcase_38 AC 192 ms
107,136 KB
testcase_39 AC 196 ms
107,132 KB
testcase_40 AC 192 ms
107,132 KB
testcase_41 AC 217 ms
107,136 KB
testcase_42 AC 192 ms
107,132 KB
testcase_43 AC 193 ms
107,260 KB
testcase_44 AC 200 ms
107,132 KB
testcase_45 AC 200 ms
107,264 KB
testcase_46 AC 199 ms
107,260 KB
testcase_47 AC 198 ms
107,260 KB
testcase_48 AC 199 ms
107,136 KB
testcase_49 AC 196 ms
107,256 KB
testcase_50 AC 196 ms
107,132 KB
testcase_51 AC 196 ms
107,260 KB
testcase_52 AC 196 ms
107,260 KB
testcase_53 AC 196 ms
107,260 KB
testcase_54 AC 555 ms
104,832 KB
testcase_55 AC 189 ms
106,396 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}




constexpr unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

constexpr int bit_ceil_log(unsigned int n) {
    int x = 0;
    while ((1 << x) < (unsigned int)(n)) x++;
    return x;
}


int main() {
    io_init();
    int N, K;
    std::cin >> N >> K;
    auto A = read_vec<int>(K);
    std::vector<int> accum(4 * N, 0);
    std::vector<int> pos;
    for (int i = 0; i < K; i++) pos.push_back(A[i]);
    for (int i = 0; i < K; i++) pos.push_back(A[i] + 2 * N);
    for (int p : pos) accum[p]++;
    for (int i = 1; i < 4 * N; i++) accum[i] += accum[i - 1];
    std::vector<ll> npos(4 * N, 4 * N);
    for (int p : pos) npos[p] = p;
    for (int i = 4 * N - 2; i >= 0; i--) {
        if (npos[i] == 4 * N) {
            npos[i] = npos[i + 1];
        }
    }
    std::array<std::vector<ll>, 20> next;
    for (int i = 0; i < 20; i++) next[i].resize(N);

    int max_log = bit_ceil_log(K + 1);

    ll L = 1, R = N / K + 1;
    while (R - L > 1) {
        ll M = (L + R) / 2;

        for (int i = 0; i < N; i++) {
            int l = i * 2;
            int r = std::max(npos[l] + 1, l + 2 * M);
            int rcnt = accum[r];
            int lcnt = (l ? accum[l - 1] : 0);
            if (rcnt - lcnt != 1) {
                next[0][i] = 2 * N;
            } else {
                next[0][i] = (r - l) / 2;
            }
        }
        
        for (int i = 1; i < max_log; i++) {
            for (int j = 0; j < N; j++) {
                ll d1 = next[i - 1][j];
                next[i][j] = d1 + next[i - 1][(j + d1) % N];
            }
        }

        bool ok = false;

        for (int l = pos[0] / 2 + 1; l <= pos[1] / 2; l++) {
            ll x = K;
            ll d = 0;
            int p = l;
            bool f = true;
            for (int i = max_log - 1; i >= 0; i--) {
                if ((x >> i) & 1) {
                    d += next[i][p];
                    p = (p + next[i][p]) % N;
                    x -= 1 << i;
                }
                if (d > N) {
                    f = false;
                    break;
                }
            }
            if (f) {
                ok = true;
                break;
            }
        }
        if (ok) L = M;
        else R = M;
    }
    std::cout << 2 * L << '\n';
}
0