QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760576 | #5426. Drain the Water Tank | einekleine18 | WA | 1ms | 3784kb | C++20 | 3.4kb | 2024-11-18 17:40:39 | 2024-11-18 17:40:40 |
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: 0
Wrong Answer
time: 1ms
memory: 3784kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'