QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183205 | #6326. Make Convex Sequence | neko_nyaa# | WA | 30ms | 9376kb | C++23 | 2.7kb | 2023-09-19 11:03:20 | 2023-09-19 11:03:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
#define int long long
bool convex(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
Point<int> A(a.first, a.second);
Point<int> B(b.first, b.second);
Point<int> C(c.first, c.second);
return A.cross(B - C) > 0;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<int> l(n), r(n);
for (int &i: l) cin >> i;
for (int &i: r) cin >> i;
vector<pair<int, int>> st;
st.push_back({r[0], 0});
st.push_back({r[1], 1});
for (int i = 2; i < n; i++) {
while (st.size() >= 2) {
int sz = st.size();
if (convex(st[sz-2], st[sz-1], {r[i], i})) break;
st.pop_back();
}
st.push_back({r[i], i});
}
vector<double> rp(n);
rp[st[0].second] = st[0].first;
for (int i = 1; i < st.size(); i++) {
int lv = st[i-1].first, rv = st[i].first;
int lid = st[i-1].second, rid = st[i].second;
double cur = lv, step = 1.0*(rv-lv)/(rid-lid);
for (int j = lid; j <= rid; j++) {
rp[j] = cur; cur += step;
}
}
//for (double i: rp) cout << i << ' ';
// cout << '\n';
const double EPS = 1e-5;
for (int i = 0; i < n; i++) {
if (rp[i] < l[i]-EPS) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3436kb
input:
4 2 1 2 5 4 6 5 8
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
3 1 4 2 3 7 4
output:
No
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 30ms
memory: 9376kb
input:
271757 150678576 28436211 82026915 150751377 329329758 207446456 449759844 245730845 425844298 93416110 220240900 414108016 268705922 158510126 362264528 715921 468258085 104286815 63874786 73971103 476243636 89261247 440888454 422989962 422041006 436065809 498263669 368104872 458751340 280953952 40...
output:
Yes
result:
wrong answer expected NO, found YES