QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#597960#9434. Italian Cuisineucup-team3877#AC ✓23ms13016kbC++2322.2kb2024-09-28 19:40:562024-09-28 19:41:03

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 19:41:03]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:13016kb
  • [2024-09-28 19:40:56]
  • 提交

answer

//line 1 "answer.cpp"
#if !__INCLUDE_LEVEL__
#include __FILE__
using lll = __int128_t;
int solve() {
    using P = Point<lll>;
    using S = Segment<lll>;
    ll n;
    input(n);
    vector<P> p;
    ll rx, ry, rd;
    input(rx, ry, rd);
    rd *= rd;
    P rp((lll)rx, (lll)ry);
    rep(i, n) {
        ll x, y;
        input(x, y);
        p.emplace_back((lll)x, (lll)y);
    }
    rep(i, n) p.push_back(p[i]);
    ll r = 0;
    lll ans = 0;
    lll total = 0;
    auto abs = [](lll x) -> lll {
        if (x < 0) return -x;
        return x;
    };
    rep(l, n) {
        chmax(r, l + 1);
        while (r < l + n) {
            S seg(p[l], p[r]);
            if (norm(rp, seg) < rd) break;
            if (ccw(p[l], rp, p[r]) == COUNTER_CLOCKWISE) break;
            auto add = cross(p[l] - p[r - 1], p[l] - p[r]);
            ans += abs(add);
            r++;
        }
        chmax(total, ans);
        ans -= abs(cross(p[l] - p[l + 1], p[l] - p[r - 1]));
    }
    print((ll)total);
    return 0;
}
int main() {
    ll t;
    input(t);
    rep(t) solve();
}
#else
//line 2 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/std.hpp"
#include <bits/stdc++.h>
#ifndef LOCAL_TEST
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // LOCAL_TEST
using namespace std;
using std::cout;
// shorten typenames
using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>;  using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>;  using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using vs = vector<string>; using vvs = vector<vector<string>>; using vvvs = vector<vector<vector<string>>>;
template<typename T> vector<vector<T>> vv(int h, int w, T val = T()) { return vector(h, vector<T>(w, val)); }
template<typename T> vector<vector<vector<T>>> vvv(int h1, int h2, int h3, T val = T()) { return vector(h1, vector(h2, vector<T>(h3, val))); }
template<typename T> vector<vector<vector<vector<T>>>> vvvv(int h1, int h2, int h3, int h4, T val = T()) { return vector(h1, vector(h2, vector(h3, vector<T>(h4, val)))); }
template <class T> using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;
// define CONSTANTS
constexpr double PI = 3.14159265358979323;
constexpr int INF = 100100111; constexpr ll INFL = 3300300300300300491LL;
float EPS = 1e-8; double EPSL = 1e-10;
template<typename T> bool eq(const T x, const T y) { return x == y; }
template<> bool eq<double>(const double x, const double y) { return (abs(x - y) < EPSL * x || abs(x - y) < EPSL); }
template<> bool eq<float>(const float x, const float y) { return abs(x - y) < EPS * x; }
template<typename T> bool neq(const T x, const T y) { return !(eq<T>(x, y)); }
template<typename T> bool ge(const T x, const T y) { return (eq<T>(x, y) || (x > y)); }
template<typename T> bool le(const T x, const T y) { return (eq<T>(x, y) || (x < y)); }
template<typename T> bool gt(const T x, const T y) { return !(le<T>(x, y)); }
template<typename T> bool lt(const T x, const T y) { return !(ge<T>(x, y)); }
constexpr int MODINT998244353 = 998244353;
constexpr int MODINT1000000007 = 1000000007;
// fasten io
struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } nyan;
// define macros
#define all(a) (a).begin(), (a).end()
#define sz(x) ((ll)(x).size())
#define rep1(n) for(ll dummy_iter = 0LL; dummy_iter < n; ++dummy_iter) // 0,1,...,n-1
#define rep2(i, n) for(ll i = 0LL, i##_counter = 0LL; i##_counter < ll(n); ++(i##_counter), (i) = i##_counter) // i=0,1,...,n-1
#define rep3(i, s, t) for(ll i = ll(s), i##_counter = ll(s); i##_counter < ll(t); ++(i##_counter), (i) = (i##_counter)) // i=s,s+1,...,t-1
#define rep4(i, s, t, step) for(ll i##_counter = step > 0 ? ll(s) : -ll(s), i##_end = step > 0 ? ll(t) : -ll(t), i##_step = abs(step), i = ll(s); i##_counter < i##_end; i##_counter += i##_step, i = step > 0 ? i##_counter : -i##_counter) // i=s,s+step,...,<t
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define repe(a, v) for(auto& a : (v)) // iterate over all elements in v
#define smod(n, m) ((((n) % (m)) + (m)) % (m))
#define sdiv(n, m) (((n) - smod(n, m)) / (m))
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());}
int Yes(bool b=true) { cout << (b ? "Yes\n" : "No\n"); return 0; };
int YES(bool b=true) { cout << (b ? "YES\n" : "NO\n"); return 0; };
int No(bool b=true) {return Yes(!b);};
int NO(bool b=true) {return YES(!b);};
template<typename T, size_t N> T max(array<T, N>& a) { return *max_element(all(a)); };
template<typename T, size_t N> T min(array<T, N>& a) { return *min_element(all(a)); };
template<typename T> T max(vector<T>& a) { return *max_element(all(a)); };
template<typename T> T min(vector<T>& a) { return *min_element(all(a)); };
template<typename T> vector<T> vec_slice(const vector<T>& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> T sum(vector<T>& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };
template<typename T> bool in_range(const T& val, const T& s, const T& t) { return s <= val && val < t; };

template <class T> inline vector<T>& operator--(vector<T>& v) { repe(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repe(x, v) ++x; return v; }

ll powm(ll a, ll n, ll mod=INFL) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % mod;
        if (n > 1) a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
ll sqrtll(ll x) {
    assert(x >= 0);
    ll rev = sqrt(x);
    while(rev * rev > x) --rev;
    while((rev+1) * (rev+1)<=x) ++rev;
    return rev;
}
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; }
int digit(ll x, int d=10) { int rev=0; while (x > 0) { rev++; x /= d;}; return rev; }
/**
 * @brief std.hpp
 * @docs docs/std/std.md
 */
//line 3 "/home/seekworser/.cpp_lib/competitive_library/competitive/geometry/base.hpp"
/**
 * @brief Pointクラス
 * @details
 * Point : 2次元空間上の点・ベクトルを扱うためのクラス
 * absもしくは単位ベクトルを使う場合はdoubleを使い、その他の場合はFracを使う
*/
template<typename T> struct Point {
    T x, y;
    Point(T x, T y) : x(x), y(y) {
    };
    Point() : Point(0, 0) {};

    Point<T> &operator+=(const Point<T>& p) { (*this).x += p.x; (*this).y += p.y; return *this; }
    Point<T> &operator-=(const Point<T>& p) { (*this).x -= p.x; (*this).y -= p.y; return *this; }
    friend Point<T> operator+(const Point<T>& lhs, const Point<T>& rhs) { return Point(lhs) += rhs; }
    friend Point<T> operator-(const Point<T>& lhs, const Point<T>& rhs) { return Point(lhs) -= rhs; }
    Point<T> &operator+() { return *this; }
    Point<T> &operator-() { (*this).x *= -1; (*this).y *= -1; return *this; }

    Point<T> &operator*=(const T &x) { (*this).x *= x; (*this).y *= x; return *this; }
    Point<T> &operator/=(const T &x) { (*this).x /= x; (*this).y /= x; return *this; }
    friend Point<T> operator*(const Point<T>& lhs, const T& rhs) { return Point(lhs) *= rhs; }
    friend Point<T> operator/(const Point<T>& lhs, const T& rhs) { return Point(lhs) /= rhs; }
    friend Point<T> operator*(const T& lhs, const Point<T>& rhs) { return Point(rhs) *= lhs; }
    friend Point<T> operator/(const T& lhs, const Point<T>& rhs) { return Point(rhs) /= lhs; }

    friend bool operator==(const Point<T> &lhs, const Point<T> &rhs) {
        return eq<T>(lhs.x, rhs.x) && eq<T>(lhs.y, rhs.y);
    }
    friend bool operator!=(const Point<T> &lhs, const Point<T> &rhs) {
        return !(lhs == rhs);
    }
    friend bool operator>(const Point<T>& lhs, const Point<T>& rhs) {
        if (eq<T>(lhs.x, rhs.x)) return gt<T>(lhs.y, rhs.y);
        return gt<T>(lhs.x, rhs.x);
    }
    friend bool operator<(const Point<T>& lhs, const Point<T>& rhs) {
        if (eq<T>(lhs.x, rhs.x)) return lt<T>(lhs.y, rhs.y);
        return lt<T>(lhs.x, rhs.x);
    }
    friend bool operator>=(const Point<T>& lhs, const Point<T>& rhs) { return !(lhs < rhs); }
    friend bool operator<=(const Point<T>& lhs, const Point<T>& rhs) { return !(lhs > rhs); }
    T dot(const Point<T> &p) const {return (*this).x * p.x + (*this).y * p.y; };
    T cross(const Point<T> &p) const {return (*this).x * p.y - (*this).y * p.x; };
    T norm() const {return (*this).dot(*this); };
    T abs() const {return sqrt((*this).norm()); };
    T arg() const {return atan((*this).y / (*this).x); };
    Point<T> rotate(const double &theta) {
        double nx = cos(theta) * (*this).x - sin(theta) * (*this).y;
        double ny = sin(theta) * (*this).x + cos(theta) * (*this).y;
        (*this).x = nx;
        (*this).y = ny;
        return (*this);
    };

    T operator*=(const Point<T>& p) const { return (*this).dot(p); }
    friend const T operator*(const Point<T>& lhs, const Point<T>& rhs) { return lhs *= rhs; }
    friend ostream& operator<<(ostream& os, const Point<T> &p) { os << p.x << " " << p.y; return os; }
};

template<typename T> T dot(const Point<T> &p1, const Point<T> &p2) { return p1.dot(p2); }
template<typename T> T cross(const Point<T> &p1, const Point<T> &p2) { return p1.cross(p2); }
template<typename T> T norm(const Point<T> &p) { return p.norm(); }
double abs(const Point<double> &p) { return p.abs(); }
Point<double> unit_vector(const Point<double> &p) { return p / abs(p); }
template<typename T> Point<T> normal_vector(const Point<double> &p) { return Point(-p.y, p.x); }
Point<double> rotate(const Point<double> &p, const double &theta) { return Point(p).rotate(theta); }

// Line : 直線クラス
template<typename T> struct Line {
    Point<T> s, t;
    Line() = default;
    Line(Point<T> s, Point<T> t) : s(s), t(t) {assert(s != t);};
    // ax+by+c=0;
    Line(T a, T b, T c) {
        assert(neq<T>(a, T(0)) || neq<T>(b, T(0)));
        if(eq<T>(b, T(0))) {
            s = Point(-c / a, T(0)); t = Point(-c / a, T(1));
        } else {
            s = Point(T(0), -c / b); t = Point(T(1), (-a-c)/b);
        }
    };
    Point<T> vec() const { return (*this).t - (*this).s; }
    Point<T> normal() const { return normal_vector((*this).vec()); }
    friend ostream& operator<<(ostream& os, const Line<T> &l) { os << l.s << " " << l.t; return os; }
};

// Segment : 線分を表す構造体
template <typename T> struct Segment : Line<T> {
    Segment() = default;
    Segment(Point<T> s, Point<T> t) : Line<T>(s, t) {}
};

// Circle : 円を表す構造体
// pが中心の位置ベクトル、rは半径
template<typename T> struct Circle {
    Point<T> o;
    T r;
    Circle() = default;
    Circle(Point<T> o, double r) : o(o), r(r) {}
};
/**
 * @brief 幾何ライブラリベースクラス
 * @docs docs/geometry/base.md
 */
//line 4 "/home/seekworser/.cpp_lib/competitive_library/competitive/geometry/counter_clockwise.hpp"
constexpr int COUNTER_CLOCKWISE = 2;
constexpr int CLOCKWISE = -2;
constexpr int ONSEGMENT = 0;
constexpr int ONLINE_BACK = 1;
constexpr int ONLINE_FRONT = -1;
template<typename T> int ccw(const Line<T> &l, const Point<T> &p, bool strict=false) {
    T crs = cross(l.vec(), p - l.s);
    if (lt<T>(crs, 0)) return CLOCKWISE;
    if (gt<T>(crs, 0)) return COUNTER_CLOCKWISE;
    T d = dot(l.vec(), p - l.s);
    if (strict) {
        if (le<T>(d, 0)) return ONLINE_BACK;
        if (ge<T>(d, norm(l.vec()))) return ONLINE_FRONT;
    } else {
        if (lt<T>(d, 0)) return ONLINE_BACK;
        if (gt<T>(d, norm(l.vec()))) return ONLINE_FRONT;
    }
    return ONSEGMENT;
};
template <typename T> int ccw(const Point<T> &p1, const Point<T> &p2, const Point<T> &p3, bool strict=false) {
    return ccw(Line<T>(p1, p2), p3, strict);
};
template <typename T> bool online(const Line<T> &l, const Point<T> &p) {
    int result = ccw(l, p);
    return -1 <= result && result <= 1;
};
template <typename T> int online(const Point<T> &p1, const Point<T> &p2, const Point<T> &p3) {
    return online(Line<T>(p1, p2), p3);
};
/**
 * @brief counter_clockwise.hpp
 * @docs docs/geometry/counter_clockwise.md
 */
//line 4 "/home/seekworser/.cpp_lib/competitive_library/competitive/geometry/angle.hpp"
constexpr int ANGLE_0 = 0;
constexpr int ANGLE_0_90 = 1;
constexpr int ANGLE_90 = 2;
constexpr int ANGLE_90_180 = 3;
constexpr int ANGLE_180 = 4;
constexpr int ANGLE_180_270 = -3;
constexpr int ANGLE_270 = -2;
constexpr int ANGLE_270_360 = -1;
template <typename T> int angle(const Point<T> &p1, const Point<T> &p2) {
    Point<T> zero(0, 0);
    assert(p1 != zero && p2 != zero);
    T d = dot(p1, p2);
    T c = cross(p1, p2);
    if (eq<T>(c, 0)) {
        if (gt<T>(d, 0)) return  ANGLE_0;
        else return ANGLE_180;
    }
    if (eq<T>(d, 0)) {
        if (gt<T>(c, 0)) return ANGLE_90;
        else return ANGLE_270;
    }
    if (gt<T>(d, 0) && gt<T>(c, 0)) return ANGLE_0_90;
    if (lt<T>(d, 0) && gt<T>(c, 0)) return ANGLE_90_180;
    if (lt<T>(d, 0) && lt<T>(c, 0)) return ANGLE_180_270;
    if (gt<T>(d, 0) && lt<T>(c, 0)) return ANGLE_270_360;
    throw runtime_error("function angle unexpectedly reached end");
};
template<typename T> int angle(const Line<T> &l1, const Line<T> &l2) { return angle(l1.vec(), l2.vec()); };
template<typename PointOrLine> bool is_parallel(const PointOrLine &p1, const PointOrLine &p2) {
    int result = angle(p1, p2);
    return result == ANGLE_0 || result == ANGLE_180;
}
template<typename PointOrLine> bool is_orthogonal(const PointOrLine &p1, const PointOrLine &p2) {
    int result = angle(p1, p2);
    return result == ANGLE_90 || result == ANGLE_270;
}
/**
 * @brief angle.hpp
 * @docs docs/geometry/angle.md
 */
//line 6 "/home/seekworser/.cpp_lib/competitive_library/competitive/geometry/intersection.hpp"
template <typename T> bool intersect(const Segment<T> &s1, const Segment<T> &s2, bool strict=false) {
    if (strict) {
        if (ccw(s1, s2.s, true) == ONSEGMENT) return online(s1, s2.t);
        if (ccw(s1, s2.t, true) == ONSEGMENT) return online(s1, s2.s);
        if (ccw(s2, s1.s, true) == ONSEGMENT) return online(s2, s1.t);
        if (ccw(s2, s1.t, true) == ONSEGMENT) return online(s2, s1.s);
        return
            ccw(s1, s2.s) * ccw(s1, s2.t) < 0 &&
            ccw(s2, s1.s) * ccw(s2, s1.t) < 0;
    }
    return
        ccw(s1, s2.s) * ccw(s1, s2.t) <= 0 &&
        ccw(s2, s1.s) * ccw(s2, s1.t) <= 0;
};
template<typename T> bool intersect(const Line<T> &l1, const Line<T> &l2) {
    if(!is_parallel(l1, l2)) return true;
    if (online(l1, l2.s)) return true;
    return false;
};
template<typename T> Point<T> cross_point(const Line<T> &l1, const Line<T> &l2) {
    assert(intersect(l1, l2));
    if(is_parallel(l1, l2)) return l1.s;
    T d1 = cross(l1.vec(), l2.vec());
    T d2 = cross(l1.vec(), l1.t - l2.s);
    return l2.s + l2.vec() * (d2 / d1);
};
template<typename T> Point<T> cross_point(const Segment<T> &s1, const Segment<T> &s2, bool strict=false) {
    assert(intersect(s1, s2, strict));
    if(is_parallel(s1, s2)) {
        if (ccw(s1, s2.s, strict) == ONSEGMENT) return s2.s;
        if (ccw(s1, s2.t, strict) == ONSEGMENT) return s2.t;
        if (ccw(s2, s1.s, strict) == ONSEGMENT) return s1.s;
        if (ccw(s2, s1.t, strict) == ONSEGMENT) return s1.t;
        throw("segments are parallel but cannot find cross point");
    }
    return cross_point(Line(s1), Line(s2));
};
/**
 * @brief intersection.hpp
 * @docs docs/geometry/intersection.md
 */
//line 6 "/home/seekworser/.cpp_lib/competitive_library/competitive/geometry/distance.hpp"
template <typename T> T norm(const Point<T> &p, const Line<T> &l) {
    T area_sq = cross(l.vec(), p - l.s);
    return area_sq * area_sq / norm(l.vec());
};
template<typename T> T norm(const Point<T> &p, const Segment<T> &s) {
    if (lt<T>(dot(s.vec(), p - s.s), 0)) return norm(p - s.s);
    if (lt<T>(dot(-s.vec(), p - s.t), 0)) return norm(p - s.t);
    return norm(p, Line<T>(s));
};
template <typename T> T norm(const Segment<T> &s1, const Segment<T> &s2) {
    if (intersect(s1, s2)) return T(0);
    T ans = norm(s1.s, s2);
    chmin(ans, norm(s1.t, s2));
    chmin(ans, norm(s2.s, s1));
    chmin(ans, norm(s2.t, s1));
    return ans;
};
double distance(const Point<double> &p, const Line<double> &l) { return sqrt(norm(p, l)); }
double distance(const Point<double> &p, const Segment<double> &s) { return sqrt(norm(p, s)); }
double distance(const Segment<double> &s1, const Segment<double> &s2) { return sqrt(norm(s1, s2)); }
template<typename T> T manhattan(const Point<T> &p) { return abs(p.x) + abs(p.y); }
template<typename T> T manhattan(const Point<T> &p1, const Point<T> &p2) { return manhattan(p1 - p2); }
/**
 * @brief distance.hpp
 * @docs docs/geometry/distance.md
 */
//line 3 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/io.hpp"
// overload operators (prototypes)
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p);
template <class T> inline istream& operator>>(istream& is, vector<T>& v);
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);

// overload operators
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repe(x, v) is >> x; return is; }
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << " " << p.second; return os; }
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { os << v.at(i); if (i != sz(v) - 1) os << " "; } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st) { ll cnt = 0; for (auto &e : st) { os << e << (++cnt != (int)st.size() ? " " : ""); } return os; }
template <typename T> ostream &operator<<(ostream &os, queue<T> q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front(); q.pop_front(); if (q.size()) os << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, stack<T> st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; }

template <typename T> int print_sep_end(string sep, string end, const T& val) { (void)sep; cout << val << end; return 0; };
template <typename T1, typename... T2> int print_sep_end(string sep, string end, const T1 &val, const T2 &...remain) {
    cout << val << sep;
    print_sep_end(sep, end, remain...);
    return 0;
};
template <typename... T> int print(const T &...args) { print_sep_end(" ", "\n", args...); return 0; };
template <typename... T> void flush() { cout << flush; };
template <typename... T> int print_and_flush(const T &...args) { print(args...); flush(); return 0; };
#define debug(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__) // debug print
template <typename T> void input(T &a) { cin >> a; };
template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };
#ifdef LOCAL_TEST
template <typename T> void debug_func(int i, const T name) { (void)i; (void)name; cerr << endl; }
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
    int scope = 0;
    for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
        cerr << name[i];
        if (name[i] == '(' || name[i] == '{') scope++;
        if (name[i] == ')' || name[i] == '}') scope--;
    }
    cerr << ":" << a << " ";
    debug_func(i + 1, name, b...);
}
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, T2 &a, T3 &...b) {
    int scope = 0;
    for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
        cerr << name[i];
        if (name[i] == '(' || name[i] == '{') scope++;
        if (name[i] == ')' || name[i] == '}') scope--;
    }
    cerr << ":" << a << " ";
    debug_func(i + 1, name, b...);
}
#endif
#ifndef LOCAL_TEST
template <typename... T>
void debug_func(T &...) {}
template <typename... T>
void debug_func(const T &...) {}
#endif
/**
 * @brief io.hpp
 * @docs docs/std/io.md
 */
//line 53 "answer.cpp"
#endif

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

output:

5
24
0

result:

ok 3 number(s): "5 24 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

1
6
0 0 499999993
197878055 -535013568
696616963 -535013568
696616963 40162440
696616963 499999993
-499999993 499999993
-499999993 -535013568

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 17ms
memory: 3576kb

input:

6666
19
-142 -128 26
-172 -74
-188 -86
-199 -157
-200 -172
-199 -186
-195 -200
-175 -197
-161 -188
-144 -177
-127 -162
-107 -144
-90 -126
-87 -116
-86 -104
-89 -97
-108 -86
-125 -80
-142 -74
-162 -72
16
-161 -161 17
-165 -190
-157 -196
-154 -197
-144 -200
-132 -200
-128 -191
-120 -172
-123 -163
-138...

output:

5093
3086
2539
668
3535
7421
4883
5711
5624
1034
2479
3920
4372
2044
4996
5070
2251
4382
4175
1489
1154
3231
4038
1631
5086
14444
1692
6066
687
1512
4849
5456
2757
8341
8557
8235
1013
5203
10853
6042
6300
4480
2303
2728
1739
2187
3385
4266
6322
909
4334
1518
948
5036
1449
2376
3180
4810
1443
1786
47...

result:

ok 6666 numbers

Test #4:

score: 0
Accepted
time: 23ms
memory: 3724kb

input:

6660
19
-689502500 -712344644 121094647
-534017213 -493851833
-578925616 -506634533
-663335128 -540066520
-748890119 -585225068
-847722967 -641694086
-916653030 -716279342
-956235261 -766049951
-1000000000 -836145979
-963288744 -923225928
-948140134 -944751289
-920681768 -972760883
-872492254 -10000...

output:

117285633945667137
89094762176992129
84336379088082383
63629451600307531
193020267813347512
73921930794195237
59524748406448173
34419869321856821
207356845785317033
185783506654647921
80463327658075813
156569165998743736
129550296314602340
157065066097450631
77819745596643484
40796197589680466
11394...

result:

ok 6660 numbers

Test #5:

score: 0
Accepted
time: 23ms
memory: 3600kb

input:

6646
17
-822557900 -719107452 81678600
-810512657 -985436857
-717822260 -1000000000
-636451281 -949735403
-599009378 -915571539
-596352662 -824307789
-736572772 -553995003
-765031367 -500309996
-797636289 -458500641
-842827212 -428669086
-871078362 -428977078
-928761972 -490982466
-999825512 -570408...

output:

110526056201314429
15027921575542560
53254517372894023
258485758440262622
34392829191543913
76614213562057620
145259866156654928
42339731416270977
143102643161355094
106105394104280855
145392090901459236
43856914998019051
173982988807640937
44231578293584008
58978505810355496
23485666110810764
12532...

result:

ok 6646 numbers

Test #6:

score: 0
Accepted
time: 23ms
memory: 3636kb

input:

6669
15
-874867377 -757943357 7111757
-974567193 -807217609
-949619167 -890139925
-934615014 -930145748
-888846948 -960741232
-795467329 -1000000000
-722124377 -940364550
-622857698 -842665231
-578818283 -747428314
-780030596 -534753737
-866558348 -484345048
-928090924 -519994734
-987269004 -5856231...

output:

182950707425830089
29338404516797685
84520746595092394
105477320399449524
73884037892247358
49031829753894899
48108760133499810
178434777514737858
31287633742235961
84173958668093920
15282003310382472
106987783997819044
50751134064267722
22920035202317059
79797616191974237
75995194318427644
94277118...

result:

ok 6669 numbers

Test #7:

score: 0
Accepted
time: 19ms
memory: 3784kb

input:

6673
11
-746998467 -874016929 25938500
-1000000000 -901415571
-645111069 -992353393
-547811885 -1000000000
-483640464 -931109189
-546643988 -877114659
-625764830 -834162211
-723093733 -813353581
-811419393 -799116488
-879584543 -791576283
-944145006 -828676656
-998000881 -880308971
14
-826271552 -81...

output:

54570343814105147
74950556637655098
38052401037814742
109159348998561498
21083015515232346
31649646072675313
42326841119894707
158636477858979605
129690295986443039
112077348808529800
16900062518936042
63732368902300348
79182769273740625
142098431062104007
111981825046535522
38580332981675983
631960...

result:

ok 6673 numbers

Test #8:

score: 0
Accepted
time: 17ms
memory: 11840kb

input:

1
100000
312059580 -177336163 523906543
43599219 998132845
43570757 998134606
43509809 998138374
43456461 998141672
43379797 998146410
43325475 998149757
43283580 998152335
43207966 998156986
43131288 998161701
43054854 998166387
42988614 998170421
42922795 998174418
42844022 998179189
42778015 9981...

output:

2336396422009996549

result:

ok 1 number(s): "2336396422009996549"

Test #9:

score: 0
Accepted
time: 21ms
memory: 11884kb

input:

1
100000
-251564816 -78082096 448753841
-80224677 990816180
-80259466 990812190
-80305475 990806906
-80353208 990801417
-80432095 990792336
-80499807 990784538
-80550474 990778690
-80584379 990774772
-80646058 990767643
-80721039 990758969
-80765340 990753844
-80831878 990746146
-80884094 990740100
...

output:

2228503226896114609

result:

ok 1 number(s): "2228503226896114609"

Test #10:

score: 0
Accepted
time: 19ms
memory: 13016kb

input:

1
100000
-21114562 65507992 38717262
185741374 -973388860
185752671 -973385638
185780414 -973377719
185856314 -973356051
185933967 -973333881
185954554 -973328000
186032784 -973305637
186080608 -973291964
186146989 -973272982
186174716 -973265053
186244761 -973245018
186322991 -973222629
186396908 -...

output:

3072519712977372770

result:

ok 1 number(s): "3072519712977372770"

Test #11:

score: 0
Accepted
time: 22ms
memory: 12916kb

input:

1
100000
268671 -2666521 876866632
230011647 -961116491
230075890 -961094782
230134968 -961074817
230168748 -961063401
230244475 -961037808
230269796 -961029249
230315761 -961013704
230385411 -960990142
230415463 -960979975
230481755 -960957543
230553370 -960933304
230586681 -960922029
230613411 -96...

output:

133463776650326652

result:

ok 1 number(s): "133463776650326652"

Test #12:

score: 0
Accepted
time: 14ms
memory: 11620kb

input:

1
100000
-2718704 778274 581723239
-978709486 169949360
-978714995 169927878
-978732247 169860576
-978751379 169785908
-978765698 169730020
-978773095 169701140
-978776354 169688400
-978789899 169635448
-978801355 169590640
-978818799 169522411
-978836755 169452110
-978848869 169404635
-978865973 16...

output:

868255658642677668

result:

ok 1 number(s): "868255658642677668"

Test #13:

score: 0
Accepted
time: 22ms
memory: 12168kb

input:

1
100000
-2748577 -2474335 98902294
951770249 -240991282
951794130 -240924574
951808902 -240883307
951834639 -240811406
951854284 -240756524
951859830 -240741030
951881397 -240680772
951908083 -240606202
951935455 -240529694
951945987 -240500253
951973326 -240423829
951997817 -240355366
952015600 -2...

output:

2586612861573259216

result:

ok 1 number(s): "2586612861573259216"

Extra Test:

score: 0
Extra Test Passed