QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760584 | #5426. Drain the Water Tank | einekleine18 | WA | 1ms | 3796kb | C++20 | 3.4kb | 2024-11-18 17:42:30 | 2024-11-18 17:42:30 |
Judging History
answer
#include <array>
#include<bits/stdc++.h>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <vector>
#define int long long
// constexpr double eps=1e-8;
// template<typename T> struct point{
// T x,y;
// bool operator==(const point &a) const {
// return std::abs(x-a.x)<=eps&&std::abs(y-a.y)<=eps;
// }
// T operator *(const point &a) const {
// return x*a.x+y*a.y;
// }
// T operator ^(const point &a) const {
// return x*a.y-y*a.x;
// }
// point operator+(const point &a) const {
// return {x+a.y,y+a.y};
// }
// point operator-(const point &a) const {
// return {x-a.y,y-a.y};
// }
// point operator-() const {
// return {-x,-y};
// }
// int toleft(const point &a)const {
// const auto t=(*this)^a;
// return (t>eps)-(t<eps);
// }
// };
// template<typename T> struct line{
// point<T>p,v;
// int toleft(const point<T>&a)const {
// return v.toleft(a-p);
// }
// };
// using Line=line<double>;
// template<typename T> struct polygon{
// std::vector<point<T>>p;
// size_t nxt(const size_t i) const {
// return i==p.size()-1?0:i+1;
// }
// std::pair<bool,int>winding(const point<T>&a) const {
// int cnt=0;
// for(size_t i=0;i<p.size();++i){
// const point<T> u=p[i],v=p[nxt(i)];
// if(std::abs((a-u)^(a-v))<=eps&&(a-u)*(a-v)<=eps){
// return {true,0};
// }
// if(std::abs(u.y-v.y)<=eps) continue;
// const Line uv={u,v-u};
// if(u.y<v.y-eps&&uv.toleft(a)<=0) continue;
// if(u.y>v.y+eps&&uv.toleft(a)>=0) continue;
// if(u.y<a.y-eps&&v.y>=a.y-eps) ++cnt;
// if(u.y>=a.y-eps&&v.y<a.y-eps) --cnt;
// }
// return {false,cnt};
// }
// };
// using ply=polygon<double>;
using a2=std::array<int, 2>;
void slove(){
int n;
std::cin>>n;
std::vector<a2>p;
for(int i=0;i<n;++i){
int a,b;
std::cin>>a>>b;
p.push_back({a,b});
}
auto get=[&](int sta)->int {
int res=0;
for(int i=0;i<n;++i){
int cur=(i+sta)%n,nxt=(i+sta+1)%n;
if(p[cur][0]>p[nxt][0]) continue;
int f=0;
// std::cout<<"s: "<<(i+sta)%n<<'\n';
while(i<n&&p[cur][1]>=p[nxt][1]){
++i;
f=1;
cur=(i+sta)%n,nxt=(i+sta+1)%n;
}
if(f){
++res;
++i;
cur=(i+sta)%n,nxt=(i+sta+1)%n;
// std::cout<<p[cur][0]<<' '<<p[cur][1]<<' '<<p[nxt][0]<<' '<<p[nxt][1]<<'\n';
while(i<n&&p[cur][1]<=p[nxt][1]){
++i;
cur=(i+sta)%n,nxt=(i+sta+1)%n;
}
--i;
}
// std::cout<<"d: "<<(i+sta)%n<<'\n';
}
return res;
};
int m=0,y=-1e5;
for(int i=0;i<n;++i){
if(p[i][1]>y){
y=p[i][1];
m=i;
}
}
int ans=get(m);
std::cout<<ans<<'\n';
}
signed main(){
#ifdef LOCAL
std::freopen("in.txt","r",stdin);
std::freopen("out.txt","w",stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int _=1;
// std::cin>>_;
for(int i=0;i<_;++i){
slove();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3512kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
8 4 4 0 4 0 2 1 2 2 2 2 0 3 0 4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
7 1 0 3 4 0 3 1 2 2 3 1 1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 0 0 170 0 140 30 60 30 0 70
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
5 0 0 1 2 1 5 0 2 0 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
3 200 0 100 100 0 0
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 50 50 100 50 100 100
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 3 0 0 4 0 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
3 10000 10000 -10000 10000 10000 9999
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
3 10000 10000 -10000 10000 10000 9900
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
3 10000 10000 9999 10000 10000 -10000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 0 0 200 0 100 173
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
3 0 0 200 0 100 1
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: -100
Wrong Answer
time: 0ms
memory: 3540kb
input:
3 -10000 -10000 10000 9999 9999 10000
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'