結果

問題 No.2343 (l+r)/2
ユーザー rniyarniya
提出日時 2023-06-09 21:56:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 7,324 bytes
コンパイル時間 5,482 ms
コンパイル使用メモリ 207,756 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-30 13:14:08
合計ジャッジ時間 3,513 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 41 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 17 ms
4,376 KB
testcase_04 AC 8 ms
4,376 KB
testcase_05 AC 4 ms
4,376 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 9 ms
4,376 KB
testcase_09 AC 6 ms
4,376 KB
testcase_10 AC 4 ms
4,380 KB
testcase_11 AC 7 ms
4,380 KB
testcase_12 AC 6 ms
4,380 KB
testcase_13 AC 5 ms
4,376 KB
testcase_14 AC 9 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <typename T> class Rational {
    T num, den;

    static T my_gcd(T x_, T y_) {
        unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
        if (!x or !y) return x + y;
        int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
        x >>= n, y >>= m;
        while (x != y) {
            if (x > y)
                x = (x - y) >> __builtin_ctzll(x - y);
            else
                y = (y - x) >> __builtin_ctzll(y - x);
        }
        return x << (n > m ? m : n);
    }

    void normalize() {
        return;  // comment out this flexibly
        T g = my_gcd(num, den);
        num /= g, den /= g;
        if (den < 0) num = -num, den = -den;
    }

public:
    Rational() {}
    Rational(T num) : num(num), den(T(1)) {}
    Rational(T num, T den) : num(num), den(den) { normalize(); }

    Rational operator+(const Rational& r) const { return Rational(num * r.den + den * r.num, den * r.den); }
    Rational operator-(const Rational& r) const { return Rational(num * r.den - den * r.num, den * r.den); }
    Rational operator*(const Rational& r) const { return Rational(num * r.num, den * r.den); }
    Rational operator/(const Rational& r) const { return Rational(num * r.den, den * r.num); }
    Rational& operator+=(const Rational& r) { return *this = *this + r; }
    Rational& operator-=(const Rational& r) { return *this = *this - r; }
    Rational& operator*=(const Rational& r) { return *this = *this * r; }
    Rational& operator/=(const Rational& r) { return *this = *this / r; }

    Rational operator+(const T& val) const { return *this + Rational(val); }
    Rational operator-(const T& val) const { return *this - Rational(val); }
    Rational operator*(const T& val) const { return *this * Rational(val); }
    Rational operator/(const T& val) const { return *this / Rational(val); }
    Rational& operator+=(const T& val) { return *this = *this + val; }
    Rational& operator-=(const T& val) { return *this = *this - val; }
    Rational& operator*=(const T& val) { return *this = *this * val; }
    Rational& operator/=(const T& val) { return *this = *this / val; }
    friend Rational operator+(const T& val, const Rational& r) { return r + val; }
    friend Rational operator-(const T& val, const Rational& r) { return r - val; }
    friend Rational operator*(const T& val, const Rational& r) { return r * val; }
    friend Rational operator/(const T& val, const Rational& r) { return r / val; }

    Rational operator-() const { return Rational(-num, den); }
    Rational abs() const { return Rational(num < 0 ? -num : num, den); }

    bool operator==(const Rational& r) const {
        if (den == 0 and r.den == 0) return num == r.num;
        if (den == 0 or r.den == 0) return false;
        return num * r.den == den * r.num;
    }
    bool operator!=(const Rational& r) const { return !(*this == r); }
    bool operator<(const Rational& r) const {
        if (den == 0 and r.den == 0) return num < r.num;
        if (den == 0) return num < 0;
        if (r.den == 0) return r.num > 0;
        return num * r.den < den * r.num;
    }
    bool operator<=(const Rational& r) const { return (*this == r) or (*this < r); }
    bool operator>(const Rational& r) const { return r < *this; }
    bool operator>=(const Rational& r) const { return (*this == r) or (*this > r); }

    bool operator==(const T& val) const { return *this == Rational(val); }
    bool operator!=(const T& val) const { return *this != Rational(val); }
    bool operator<(const T& val) const { return *this < Rational(val); }
    bool operator<=(const T& val) const { return *this <= Rational(val); }
    bool operator>(const T& val) const { return *this > Rational(val); }
    bool operator>=(const T& val) const { return *this >= Rational(val); }
    friend bool operator==(const T& val, const Rational& r) { return r == val; }
    friend bool operator!=(const T& val, const Rational& r) { return r != val; }
    friend bool operator<(const T& val, const Rational& r) { return r > val; }
    friend bool operator<=(const T& val, const Rational& r) { return r >= val; }
    friend bool operator>(const T& val, const Rational& r) { return r < val; }
    friend bool operator>=(const T& val, const Rational& r) { return r <= val; }

    explicit operator double() const { return (double)num / (double)den; }
    explicit operator long double() const { return (long double)num / (long double)den; }
    friend std::ostream& operator<<(std::ostream& os, const Rational& r) { return os << r.num << '/' << r.den; }
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

bool tle(int N, const vector<int>& A) {
    bool res = false;
    auto dfs = [&](auto self, vector<Rational<int>> cur) {
        if (res) return;
        int len = cur.size();
        if (len == 1) {
            if (cur[0] == Rational<int>(1, 2)) res = true;
            return;
        }
        for (int i = 0; i + 1 < len; i++) {
            vector<Rational<int>> nxt;
            for (int j = 0; j < i; j++) nxt.emplace_back(cur[j]);
            nxt.emplace_back((cur[i] + cur[i + 1]) / 2);
            for (int j = i + 2; j < len; j++) nxt.emplace_back(cur[j]);
            self(self, nxt);
        }
    };
    vector<Rational<int>> init;
    for (const int& x : A) init.emplace_back(x);
    dfs(dfs, init);
    return res;
}

bool solve(int N, const vector<int>& A) {
    vector<pair<int, int>> v;
    for (int i = 1, cnt = 1; i <= N; i++) {
        if (i == N or A[i] != A[i - 1]) {
            v.emplace_back(A[i - 1], cnt);
            cnt = 1;
        } else
            cnt++;
    }
    int len = v.size();
    if (~len & 1) return true;
    for (int i = 1; i < len; i += 2) {
        if (v[i].second > 1) {
            return true;
        }
    }
    return len >= 9;
}

void experiment() {
    int N;
    cin >> N;
    for (int mask = 0; mask < 1 << N; mask++) {
        vector<int> A;
        for (int i = 0; i < N; i++) A.emplace_back(mask >> i & 1);
        if (not(solve(N, A) == tle(N, A))) {
            debug(N, A);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (; T--;) {
        int N;
        cin >> N;
        vector<int> A(N);
        cin >> A;
        cout << (solve(N, A) ? "Yes\n" : "No\n");
    }
    return 0;
}
0