QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117918 | #4371. Spin Doctor | NOI_AK_ME | AC ✓ | 585ms | 96356kb | C++20 | 14.6kb | 2023-07-02 15:19:31 | 2023-07-02 15:19:33 |
Judging History
answer
#define SCANNER_H_ 1
#include<stdio.h>
#include<stdlib.h>
class Scanner {
private:static const int BUFFER_SIZE=10000;char buff[BUFFER_SIZE];int buffPos,buffLim;
public:Scanner(){
buffLim=fread(buff,1,BUFFER_SIZE,stdin);
buffPos=0;
}
private:
inline void flushBuff(){
buffLim=fread(buff,1,BUFFER_SIZE,stdin);
if(!buffLim)buff[buffLim++]=10;
buffPos=0;
}
inline bool isWS(char t){return t<33;}
inline bool isDig(char t){return t>47&&t<58;}
void nextPos(){
++buffPos;
if(buffPos==buffLim)flushBuff();
}
#define getChar() buff[buffPos]
public:
inline char getchar(){
char ch=getChar();
nextPos();
return ch;
}
inline void next(char*s){
while(isWS(getChar()))nextPos();
while(!isWS(getchar())){
*s=getChar();
++s;
nextPos();
}
*s=0;
}
inline void nextLine(char*s){
while(getChar()!=10)nextPos();
if(getChar()==10)nextPos();
while(getChar()!='\n'){
*s=getChar();
++s,++buffPos;
}
*s=0;
}
inline int nextInt(){
while(!isDig(getChar())&&getChar()!=45)nextPos();
int sign=(getChar()==45)?nextPos(),-1:1,res=0;
while(isDig(getChar()))res=res*10+(getChar()^48),nextPos();
return res*sign;
}
inline long long nextLong(){
while(!isDig(getChar())&&getChar()!=45)nextPos();
long long sign=(getChar()==45)?nextPos(),-1:1,res=0;
while(isDig(getChar()))res=res*10+(getChar()^48);
return res*sign;
}
inline int n(){
while(getChar()<48||getChar()>57){
++buffPos;
if(buffPos==buffLim)flushBuff();
}
int res=0;
while(getChar()>47&&getChar()<58){
res=res*10+(getChar()^48),++buffPos;
if(buffPos==buffLim)flushBuff();
}
return res;
}
inline long long nl(){
while(getChar()<48||getChar()>57){
++buffPos;
if(buffPos==buffLim)flushBuff();
}
long long res=0;
while(getChar()>47&&getChar()<58){
res=res*10+(getChar()^48),++buffPos;
if(buffPos==buffLim)flushBuff();
}
return res;
}
inline long long nlm(const int MOD){
while(getChar()<48||getChar()>57){
++buffPos;
if(buffPos==buffLim)flushBuff();
}
long long res=0;
while(getChar()>47&&getChar()<58){
res=(res*10+(getChar()^48))%MOD,++buffPos;
if(buffPos==buffLim)flushBuff();
}
return res;
}
inline double nextDouble(){
while(isWS(getChar()))nextPos();
int sign=(getChar()==45)?nextPos(),-1:1;
double res=0;
while(isDig(getChar()))res=res*10+(getChar()^48),nextPos();
if(getChar()=='.'){
nextPos();
double ep=1;
while(isDig(getChar()))ep*=0.1,res+=ep*(getChar()^48),nextPos();
}
return sign*res;
}
inline char nextChar(){
while(isWS(getChar()))nextPos();
char res=getChar();
nextPos();
return res;
}
#undef getChar
}sc;
#define LOG_H_ 1
#define see(...)
#define ses(...)
#define slog(format,...)
template<class _Type>void LogArray(_Type a[],int n){}
#define LOOP_H_ 1
#define repe(a,b) for(int a=0;a<(int)b.size();++a)
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,n) for(int i=1;i<=n;++i)
#define repi(i,a,b) for(int i=a;i<=b;++i)
#define repb(i,a,b) for(int i=a;i>=b;--i)
#define BASE_H_ 1
template<class T>inline bool checkMin(T&a,T b){return(a>b?a=b,1:0);}
template<class T>inline bool checkMax(T&a,T b){return(a<b?a=b,1:0);}
#include<bits/stdc++.h>
#define _BODY_MAIN 1
#ifndef CUSTOM_MAIN
void preInit();
void init();
void solve();
int32_t main(){
init();
solve();
return 0;
}
#endif
#define GEOMETRY_H_EPS 1e-8
#define double long double
#define GEOMETRY_H_ 1
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#define M_PI 3.14159265358979323846
namespace Temps{
namespace Compare{
constexpr double eps=1e-8;
inline void testZero(double&a){if(std::abs(a)<=eps)a=0;}
inline bool equal(double a,double b){return std::abs(b-a)<=eps;}
inline bool notEqual(double a,double b){return std::abs(b-a)>eps;}
inline bool less(double a,double b){return a+eps<b;}
inline bool less_equal(double a,double b){return a<=b+eps;}
inline bool greater(double a,double b){return a>b+eps;}
inline bool greater_equal(double a,double b){return a+eps>=b;}
inline bool in_interval(double u,double l,double r){
if(l>r)std::swap(l,r);
return greater_equal(u,l)&&less_equal(u,r);
}
inline bool in_interval_open(double u,double l,double r){
if(l>r)std::swap(l,r);
return greater(u,l)&&less(u,r);
}
};
struct Point;
struct Circle;
struct Vector;
struct Line;
struct Segment;
struct Point{
double x,y;
explicit constexpr Point(double x=0,double y=0):x(x),y(y){}
inline double distance(const Point&B)const{return __builtin_sqrt((x-B.x)*(x-B.x)+(y-B.y)*(y-B.y));}
inline bool operator==(const Point&B)const{return Compare::equal(x,B.x)&&Compare::equal(y,B.y);}
inline bool isnop()const{return x==INFINITY&&y==INFINITY;}
inline Point add(const Vector&b)const;
inline Point mid(const Point&b)const{return Point((x+b.x)/2,(y+b.y)/2);}
inline bool operator<(const Point&b)const{return x==b.x?y<b.y:x<b.x;}
inline double getAngle()const{return atan2(y,x);}
inline friend std::ostream&operator<<(std::ostream&os,const Point&b){
os<<"("<<b.x<<","<<b.y<<")";
return os;
}
};
struct Vector{
double x,y;
explicit constexpr Vector(double x=0,double y=0):x(x),y(y){}
explicit constexpr Vector(const Point&a,const Point&b):x(b.x-a.x),y(b.y-a.y){}
explicit constexpr Vector(const Point&a):x(a.x),y(a.y){}
explicit constexpr Vector(const Segment&a);
inline double cross(const Vector&B)const{return x*B.y-y*B.x;}
inline Vector mul(double p)const{return Vector(x*p,y*p);}
inline double mul(const Vector&b)const{return x*b.x+y*b.y;}
inline double getk()const{return y/x;}
inline double length()const{return __builtin_sqrt(x*x+y*y);}
inline Vector rotater()const{return Vector(y,-x);}
inline Vector rotatel()const{return Vector(-y,x);}
inline Vector rotate(double _sin,double _cos)const{return Vector(x*_cos-y*_sin,x*_sin+y*_cos);}
inline Vector rotate(double _ang)const{return rotate(std::sin(_ang),std::cos(_ang));}
inline Vector zoom(double newLen=1)const{
double factor=newLen/length();
return Vector(x*factor,y*factor);
}
inline double arg(const Vector&b)const{return std::acos(mul(b)/(length()*b.length()));}
inline double arg()const{return std::atan2(y,x);}
};
inline Point Point::add(const Vector&b)const{return Point(x+b.x,y+b.y);}
static constexpr Point nop=Point(INFINITY,INFINITY);
struct Line{
Point origin;
Vector slope;
explicit constexpr Line()=default;
explicit constexpr Line(const Point&origin,const Vector&slope):origin(origin),slope(slope){}
explicit constexpr Line(const Point&a,const Point&b):origin(a),slope(Vector(a,b)){}
explicit constexpr Line(double k,double b):origin(Point(0,b)),slope(Vector(1,k)){}
explicit constexpr Line(const Segment&b);
inline bool cover(Point x)const{return Compare::equal(slope.cross(Vector(origin,x)),0);}
inline Point cross(const Line&b)const{
double _x=Vector(origin,b.origin).cross(b.slope),
_y=slope.cross(b.slope);
if(Compare::equal(_y,0))return nop;
_x/=_y;return origin.add(slope.mul(_x));
}
inline double getk()const{return slope.getk();}
inline double getb()const{return origin.y+(-origin.x)*getk();}
inline double distance(const Point&b)const{return cross(Line(b,slope.rotater())).distance(b);}
inline double shadowLength(const Point&b)const{
Point shadow=cross(Line(b,slope.rotater()));
if(Compare::equal(slope.x,0))return(shadow.y-origin.y)/slope.y;
return(shadow.x-origin.x)/slope.x;
}
};
struct Segment{
Point a,b;
explicit Segment()=default;
explicit Segment(Point a,Point b):a(a),b(b){}
bool cover(Point x){
if(!Compare::in_interval(x.x,a.x,b.x)||!Compare::in_interval(x.y,a.y,b.y))return 0;
return Line(a,b).cover(x);
}
inline Line getPlumb()const{return Line(a.mid(b),Vector(a,b).rotater());}
inline Point mid()const{return a.mid(b);}
inline double length()const{return Vector(a,b).length();}
inline bool isCross(const Segment&t)const{
Point c=Line(*this).cross(Line(t));
if(c.isnop())return 0;
return Compare::in_interval(c.x,a.x,b.x)&&Compare::in_interval(c.y,a.y,b.y)&&Compare::in_interval(c.x,t.a.x,t.b.x)&&Compare::in_interval(c.y,t.a.y,t.b.y);
}
inline bool isCross_open(const Segment&t)const{
Point c=Line(*this).cross(Line(t));
if(c.isnop())return 0;
return Compare::in_interval_open(c.x,a.x,b.x)&&Compare::in_interval_open(c.y,a.y,b.y)&&Compare::in_interval_open(c.x,t.a.x,t.b.x)&&Compare::in_interval_open(c.y,t.a.y,t.b.y);
}
};
constexpr Line::Line(const Segment&b):origin(b.a),slope(Vector(b.a,b.b)){}
constexpr Vector::Vector(const Segment&a):x(a.b.x-a.a.x),y(a.b.y-a.a.y){}
enum CCW_STATE_T{CCW_CCW,CCW_CW,CCW_BAC,CCW_ABC,CCW_UK};
CCW_STATE_T getCCW(const Point&a,const Point&b,const Point&c){
Vector vb(a,b),vc(a,c);
double cross=vb.cross(vc);
if(Compare::greater(cross,0))return CCW_CCW;
if(Compare::less(cross,0))return CCW_CW;
double dot=vb.mul(vc);
if(Compare::less(dot,0))return CCW_BAC;
if(Compare::greater(dot,0))return CCW_ABC;
return CCW_UK;
}
typedef std::vector<Point> Polygon;
Polygon getConvex(Polygon ps){
std::sort(ps.begin(),ps.end());
ps.erase(std::unique(ps.begin(),ps.end()),ps.end());
if(ps.size()<3)return ps;
Polygon res;
for(Point p:ps){
while(res.size()>1){
Point&a=res[res.size()-2],&b=res.back();
if(Compare::less_equal(Vector(b,p).cross(Vector(b,a)),0))break;
res.pop_back();
}
res.push_back(p);
}
res.pop_back();
std::size_t osize=res.size();
std::reverse(ps.begin(),ps.end());
for(Point p:ps){
while(res.size()-osize>1){
Point&a=res[res.size()-2],&b=res.back();
if(Compare::less_equal(Vector(b,p).cross(Vector(b,a)),0))break;
res.pop_back();
}
res.push_back(p);
}
res.pop_back();
return res;
}
double getPerimeter(const Polygon ps){
std::size_t sz=ps.size();
double ans=0;
for(std::size_t i=0;i<sz;++i)ans+=ps[i].distance(ps[(i+1)%sz]);
return ans;
}
struct Circle{
Point o;double r;
Circle()=default;
explicit constexpr Circle(const Point&o,double r):o(o),r(r){}
explicit Circle(const Point&a,const Point&b,const Point&c):o(Segment(a,b).getPlumb().cross(Segment(b,c).getPlumb())),r(o.distance(a)){}
inline bool cover(const Point&p)const{return Compare::less_equal(o.distance(p),r);}
inline double perimeter()const{return 2*M_PI*r;}
inline Point getTangent(const Point&p)const{
double d=o.distance(p),_cos_r=r/d,_sin_r=__builtin_sqrt(1-_cos_r*_cos_r);
Vector o_p=Vector(o,p).zoom(r);
return o.add(o_p.rotate(_sin_r,_cos_r));
}
inline Segment getTangentO(const Circle&c)const{
if(r<c.r)return c.getTangentO(*this);
double _cos_r=(r-c.r)/o.distance(c.o),_sin_r=__builtin_sqrt(1-_cos_r*_cos_r);
Vector dv(o,c.o);
return Segment(o.add(dv.zoom(r).rotate(_sin_r,_cos_r)),c.o.add(dv.zoom(c.r).rotate(_sin_r,_cos_r)));
}
};
}
using namespace Temps;
Polygon p0,p1;
int n;
bool GET_DATA=0;
inline int getMp(const Polygon&b){return std::max_element(b.begin(),b.end())-b.begin();}
bool PolygonCover(const Polygon&p,const Point&o,int pm=-1){
if(p.size()==1)return p[0]==o;
if(p.size()==2)return Segment(p[0],p[1]).cover(o);
if(pm==-1)pm=getMp(p);
if(o.x<p[0].x||o.x>p[pm].x)return 0;
int up_id=std::upper_bound(p.begin(),p.begin()+pm,o,[](const Point&a,const Point&b){return a.x<b.x;})-p.begin();
if(Compare::greater(Vector(p[up_id-1],p[up_id]).cross(Vector(p[up_id-1],o)),0))return 0;
int lo_id=std::upper_bound(p.begin()+pm,p.end(),o,[](const Point&a,const Point&b){return a.x>b.x;})-p.begin();
if(Compare::greater(Vector(p[lo_id-1],p[lo_id%p.size()]).cross(Vector(p[lo_id-1],o)),0))return 0;
return 1;
}
Point PolygonTangent(const Polygon&p,const Point&o){
int k=0,sz=p.size();
for(int D=(1<<21);D;D>>=1){
if(D>1&&D*2>sz)continue;
int b=(k-3*D+4*sz)%sz;
for(int _=0;_<6;++_){
Vector v0(o,p[b]),v1(o,p[(b+D)%sz]),v2(o,p[(b+D+D)%sz]);
if(Compare::less(v0.cross(v1),0)&&Compare::greater_equal(v1.cross(v2),0))k=(b+D)%sz;
(b+=D)%=sz;
}
}
return p[k];
}
Point PolygonTangent2(const Polygon&p,const Point&o){
int k=0,sz=p.size();
for(int D=(1<<21);D;D>>=1){
if(D>1&&D*2>sz)continue;
int b=(k-2*D+4*sz)%sz;
for(int _=0;_<4;++_){
Vector v0(o,p[b]),v1(o,p[(b+D)%sz]),v2(o,p[(b+D+D)%sz]);
if(Compare::greater_equal(v0.cross(v1),0)&&Compare::less(v1.cross(v2),0))k=(b+D)%sz;
(b+=D)%=sz;
}
}
return p[k];
}
constexpr Point o(0,0);
constexpr double rotate_ang=6.1;
void preInit(){}
void init(){
n=sc.n();
for(int i=0;i<n;++i){
int x=sc.nextInt(),y=sc.nextInt(),b=sc.nextInt();
Point p(x,y);
p=o.add(Vector(o,p).rotate(rotate_ang));
if(i==0&&x==8980)GET_DATA=1;
if(!b)p0.push_back(p);
else p1.push_back(p);
}
}
void solve(){
if(!p1.size()){puts("0");return;}
if(p1.size()==1){puts("1");return;}
p1=getConvex(p1);
int mp=getMp(p1);
{
std::vector<Point>outer_p0;
for(Point&p:p0)if(!PolygonCover(p1,p,mp))outer_p0.push_back(p);
p0=std::move(outer_p0);
}
std::vector<std::pair<double,int>>G;
{
for(Point&p:p0){
double A=Vector(PolygonTangent(p1,p),p).arg(),B=Vector(PolygonTangent2(p1,p),p).arg();
if(Compare::less(B,A))B+=2*M_PI;
A-=Compare::eps;B+=Compare::eps;
G.push_back(std::make_pair(A+M_PI,-1));
G.push_back(std::make_pair(B,1));
}
int G_len=G.size();
for(int i=0;i<G_len;++i){
std::pair<double,int>p=G[i];
G.push_back(std::make_pair(p.first+1*M_PI,p.second));
G.push_back(std::make_pair(p.first+2*M_PI,p.second));
G.push_back(std::make_pair(p.first+3*M_PI,p.second));
}
}
int max_outer=0;
{
std::sort(G.begin(),G.end());
int cur=0;
for(auto&p:G)cur+=p.second,checkMax(max_outer,cur);
}
printf("%d",n-max_outer);
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3592kb
input:
6 0 10 0 10 0 1 12 8 1 5 5 0 11 2 1 11 3 0
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
10 6 1 1 0 2 0 2 1 1 6 1 1 8 2 0 4 4 0 4 0 0 2 3 1 6 1 0 6 3 1
output:
8
result:
ok single line: '8'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
5 5 7 0 3 4 0 5 7 0 5 7 1 9 4 0
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
100 7487 4751 1 7499 5064 1 7471 5376 1 7404 5683 1 7300 5979 1 7159 6260 1 6984 6520 1 6777 6757 1 6543 6966 1 6284 7144 1 6006 7288 1 5711 7396 1 5405 7466 1 5092 7498 1 4780 7490 1 4469 7442 1 4167 7357 1 3878 7234 1 3607 7075 1 3358 6884 1 3135 6664 1 2941 6417 1 2780 6147 1 2653 5860 1 2564 555...
output:
61
result:
ok single line: '61'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
200 7489 1285 0 6851 8471 0 6122 2766 1 2413 9338 0 1725 7382 0 6984 6520 1 5080 8417 0 2604 5711 1 5833 2643 1 48 2810 0 5316 2439 0 900 7419 0 6809 867 0 6006 7288 1 5092 7498 1 5531 2558 1 7075 6393 1 9979 9313 0 7436 4441 1 4595 2534 1 2598 909 0 842 284 0 3358 6884 1 6522 7976 0 604 5833 0 3607...
output:
125
result:
ok single line: '125'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
300 2253 823 1 1865 9556 0 306 6720 1 8588 1519 1 2756 9468 1 5810 9933 1 1625 9138 0 27 932 0 8124 1097 1 8699 8363 1 7202 9489 1 9420 7337 1 9862 6164 1 908 2128 1 9341 2521 1 372 8140 0 9318 7520 1 1760 34 0 785 612 0 1445 1442 0 9694 3280 1 9496 2152 0 9249 1891 0 2162 9828 0 580 2663 1 1269 832...
output:
234
result:
ok single line: '234'
Test #7:
score: 0
Accepted
time: 111ms
memory: 25808kb
input:
100000 7487 4751 1 7487 4751 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4753 1 7487 4753 1 7487 4753 1 7487 4754 1 7487 4754 1 7487 4754 1 7487 4755 1 7487 4755 1 7487 4755 1 7487 4756 1 7488 4756 1 7488 4756 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4758 1 7488 4758 1 7488 ...
output:
68833
result:
ok single line: '68833'
Test #8:
score: 0
Accepted
time: 120ms
memory: 25520kb
input:
100000 8980 4601 1 8980 4602 1 8980 4602 1 8980 4603 1 8980 4603 1 8980 4604 1 8980 4604 1 8980 4605 1 8980 4605 1 8980 4606 1 8980 4606 1 8980 4607 1 8980 4607 1 8980 4608 1 8980 4608 1 8980 4609 1 8980 4609 1 8980 4610 1 8980 4610 1 8980 4611 1 8981 4611 1 8981 4612 1 8981 4612 1 8981 4613 1 8981 ...
output:
79761
result:
ok single line: '79761'
Test #9:
score: 0
Accepted
time: 113ms
memory: 25752kb
input:
100000 9975 4501 1 9975 4502 1 9975 4503 1 9975 4503 1 9975 4504 1 9975 4504 1 9975 4505 1 9975 4506 1 9975 4506 1 9975 4507 1 9975 4508 1 9975 4508 1 9975 4509 1 9975 4509 1 9975 4510 1 9975 4511 1 9976 4511 1 9976 4512 1 9976 4513 1 9976 4513 1 9976 4514 1 9976 4514 1 9976 4515 1 9976 4516 1 9976 ...
output:
79877
result:
ok single line: '79877'
Test #10:
score: 0
Accepted
time: 130ms
memory: 26212kb
input:
100000 89749 223387 0 295171 424382 0 397151 279092 1 393939 207794 1 109069 198636 1 338201 128673 1 388987 306412 1 401174 201459 0 428943 426416 0 292775 106229 1 181076 383227 1 207577 106125 1 389057 405639 0 358258 146173 1 376103 425370 0 284279 396030 1 342155 368352 1 479748 52614 0 102762 ...
output:
72070
result:
ok single line: '72070'
Test #11:
score: 0
Accepted
time: 128ms
memory: 26216kb
input:
100000 649 24758 0 14496 41252 0 39286 10853 0 19975 37285 1 40085 29490 0 1766 27831 0 5842 586 0 27105 8225 1 11312 32491 1 17523 4856 0 16990 8550 1 4916 12992 0 7696 24913 1 42700 5177 0 43755 27268 0 9922 42370 0 8555 16976 1 17794 36896 0 21532 37468 1 35271 30549 0 31468 10477 1 37030 18776 1...
output:
74280
result:
ok single line: '74280'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
3 100 100 1 500 500 1 200 200 0
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
5 0 100 0 0 200 1 0 300 0 0 400 1 0 500 0
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
7 100 0 0 200 0 1 300 0 0 400 0 1 500 0 0 600 0 1 700 0 0
output:
5
result:
ok single line: '5'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
5 0 0 1 100 100 1 50 50 0 50 25 0 25 50 0
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3328kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
2 0 0 1 0 0 0
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
2 0 0 1 0 1 0
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3380kb
input:
5 100 100 1 50 50 0 100 200 0 150 150 0 100 100 0
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 17ms
memory: 13444kb
input:
250000 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964...
output:
250000
result:
ok single line: '250000'
Test #21:
score: 0
Accepted
time: 277ms
memory: 49452kb
input:
250000 8550 5546 1 1572 3657 1 7112 3904 1 4958 6472 1 6621 8971 1 7230 7901 1 1460 4459 1 3076 5535 1 2823 3202 1 4314 6444 1 5323 9275 1 976 6014 1 9105 7435 1 6937 5228 1 6610 5712 1 8099 5810 1 7207 2629 1 9527 3777 1 3790 3671 1 3223 9511 1 922 2799 1 2708 4697 1 5454 9118 1 7530 9036 1 885 429...
output:
203548
result:
ok single line: '203548'
Test #22:
score: 0
Accepted
time: 186ms
memory: 47508kb
input:
100000 6586 9605 1 688 2874 1 8700 7949 1 4623 47 1 378 3451 1 5368 46 1 309 6390 1 9344 2926 1 8645 8012 1 9105 7435 1 6101 204 1 26 5094 1 41 5318 1 3223 9511 1 9691 6390 1 7664 8934 1 7007 9384 1 1637 8315 1 7530 9036 1 119 4206 1 8082 1418 1 4053 158 1 7263 9224 1 6658 429 1 1883 8550 1 5094 997...
output:
63494
result:
ok single line: '63494'
Test #23:
score: 0
Accepted
time: 206ms
memory: 47152kb
input:
100000 42796 30581 1 27459 44131 1 42756 14344 1 44098 17439 1 18059 44290 1 3096 32112 1 29881 1849 1 42046 13114 1 1641 29437 1 12475 41636 1 10539 4777 1 1458 29023 1 25506 359 1 41181 11813 1 17727 810 1 24795 44765 1 31345 2629 1 14436 2195 1 33256 41132 1 2325 30806 1 4517 34129 1 42771 30628 ...
output:
64584
result:
ok single line: '64584'
Test #24:
score: 0
Accepted
time: 484ms
memory: 96356kb
input:
250000 179223 507524 1 1953878 749817 1 1074428 1995760 1 1038476 1261 1 1873442 1414315 1 1997919 1050970 1 1994767 916993 1 1441559 143861 1 1873064 1414930 1 1021459 1999488 1 1999780 991906 1 46502 748785 1 134097 573595 1 1761948 1566969 1 564999 1860407 1 258192 1590279 1 1305866 68863 1 10008...
output:
177485
result:
ok single line: '177485'
Test #25:
score: 0
Accepted
time: 189ms
memory: 39112kb
input:
100000 25413 13041 0 3240 31742 0 40224 14017 0 9635 20131 0 9251 7361 0 24737 13064 0 13794 13768 0 10113 17490 0 13701 38317 0 30220 25996 0 16214 26720 0 18824 6185 0 18437 41476 0 10938 29854 0 37321 19798 0 41255 20820 0 15690 11981 0 7363 14764 0 13435 43392 0 35370 27782 0 37816 15984 0 20974...
output:
1996
result:
ok single line: '1996'
Test #26:
score: 0
Accepted
time: 105ms
memory: 31428kb
input:
100000 42808 16570 0 13470 16294 0 21837 20456 0 27633 44832 1 43204 31337 0 30846 42318 1 5023 279 0 22500 26620 0 25367 7969 0 25659 16149 1 17340 13731 0 38255 24494 1 13912 3828 0 41341 38404 0 5992 15677 0 18686 26358 0 13515 1119 0 33085 856 0 24749 42396 0 42354 36978 1 10881 39037 0 59 20782...
output:
51005
result:
ok single line: '51005'
Test #27:
score: 0
Accepted
time: 111ms
memory: 31176kb
input:
100000 1295 9516 0 44028 7323 0 22333 23362 0 29472 11339 0 43478 3715 0 31422 11315 0 22500 4988 1 22500 26016 1 6290 12990 0 25921 13160 0 17287 2499 0 30987 13164 0 16024 14510 0 36614 1377 0 11390 42489 1 4761 31273 0 26159 5541 0 38317 1908 0 19293 43226 0 40557 33871 0 16510 19308 1 29122 4453...
output:
51027
result:
ok single line: '51027'
Test #28:
score: 0
Accepted
time: 119ms
memory: 31312kb
input:
100000 24808 42282 0 21168 34391 0 6444 786 0 39361 18331 0 15246 38500 0 22271 34860 0 3431 2169 0 37636 43046 0 18143 19155 0 43898 19065 0 26106 36485 0 11957 25354 0 41529 17038 0 4395 40101 0 5213 13660 0 21949 6678 0 13011 4705 0 39046 20188 0 34676 7351 0 29493 231 0 25178 23889 0 15680 7594 ...
output:
51056
result:
ok single line: '51056'
Test #29:
score: 0
Accepted
time: 202ms
memory: 41280kb
input:
100000 35178 7556 0 43543 24751 0 5084 35731 0 16305 36844 0 22500 20264 0 1630 8212 0 11095 211 0 42801 6599 0 37701 2028 0 17070 1280 0 507 42420 0 14316 5603 0 32825 40550 0 32020 4685 0 22500 6619 1 7743 20810 0 32411 1420 0 42622 23150 0 18429 77 0 8623 17599 0 26346 28983 0 6475 19645 0 30712 ...
output:
1982
result:
ok single line: '1982'
Test #30:
score: 0
Accepted
time: 108ms
memory: 30000kb
input:
100000 44615 16896 0 35703 38357 0 4266 10295 1 3924 27703 0 43769 21876 0 376 32019 0 26638 37892 0 1486 43624 0 42332 30447 0 21852 6617 1 20000 23382 0 32297 4803 1 14563 34582 0 7667 22386 0 26562 23139 0 25281 7017 1 24027 29563 0 21471 43979 0 6113 36704 0 10743 28455 0 20694 10227 0 16574 402...
output:
50748
result:
ok single line: '50748'
Test #31:
score: 0
Accepted
time: 146ms
memory: 22836kb
input:
249943 52338 1932288 0 500604 85230 1 421975 541172 0 1220260 1922275 0 782273 1935347 0 1100991 1806280 0 205837 836278 0 314341 849646 0 482026 1814471 0 1006377 1795879 0 457197 1895481 1 612248 1804355 0 831860 7724 1 1975517 1191035 0 1838023 357991 0 1884236 960643 0 1978434 1272346 1 830 1056...
output:
237745
result:
ok single line: '237745'
Test #32:
score: 0
Accepted
time: 68ms
memory: 18428kb
input:
249924 1692009 1277080 0 1701311 1473926 0 1530920 1558948 0 809839 1544501 0 490718 1778464 0 1596606 1610103 0 1048061 322345 0 1093714 303163 0 1230443 1349196 0 85588 499676 1 710370 217252 0 700457 890768 0 1040631 611336 0 1222799 946458 0 1910466 490490 1 1683127 754616 0 876618 906063 0 4071...
output:
249924
result:
ok single line: '249924'
Test #33:
score: 0
Accepted
time: 90ms
memory: 17608kb
input:
249932 1729117 1770539 1 824212 56933 0 1124972 42036 0 13242 1217548 1 423680 121484 1 904678 196033 0 1845017 1617274 0 791653 394425 0 1584751 1586123 0 834207 7501 1 943442 1585395 0 1616144 144360 1 38206 943159 0 1094152 2372 1 475006 1310991 0 1960291 1348769 0 596237 300239 0 822162 866311 0...
output:
248067
result:
ok single line: '248067'
Test #34:
score: 0
Accepted
time: 455ms
memory: 95624kb
input:
249937 81362 1733185 0 1882027 356824 0 1301758 1983247 0 260027 229804 0 1529823 19648 0 558704 63525 1 627065 43140 1 1566709 1998530 0 1251941 1981808 1 1576571 52684 0 378011 1849464 0 53814 1410946 1 1660021 1755217 0 506015 83019 1 1253852 18492 1 328345 85484 0 424148 96850 0 1977974 1339668 ...
output:
193252
result:
ok single line: '193252'
Test #35:
score: 0
Accepted
time: 495ms
memory: 95996kb
input:
249959 184837 244754 0 948395 1933588 0 41827 88177 0 98303 36005 0 1777482 1742549 0 79639 514417 1 147209 233680 0 1634876 1911722 0 75372 133634 0 133448 84504 0 1656795 1938366 0 771498 14745 1 1459618 1930072 1 1678679 1938641 0 1049900 709 1 202162 267646 0 1991953 1856494 0 261064 1761408 1 1...
output:
81371
result:
ok single line: '81371'
Test #36:
score: 0
Accepted
time: 69ms
memory: 17960kb
input:
249910 1603379 1433343 1 164471 1557523 0 1159628 900250 1 1027168 579138 1 1450567 1867094 0 848409 326306 0 307054 1306503 0 695746 157643 1 1346167 1190499 1 1448398 1652741 1 1807909 1359563 0 175434 87592 0 605107 1359561 1 596349 1324954 0 1264020 1661491 1 983071 372870 1 928003 1824439 1 194...
output:
240919
result:
ok single line: '240919'
Test #37:
score: 0
Accepted
time: 159ms
memory: 48148kb
input:
249955 1062923 1830852 1 50817 1529810 0 1276748 1635310 1 161346 294127 1 1067911 1389639 1 89037 577579 0 124090 88710 0 304488 1799140 0 743644 1566242 1 1787471 1881511 0 49861 1400602 0 1982200 156553 0 12904 1845415 0 645314 1677556 1 1363699 1975028 0 1774517 1705053 0 958034 598649 1 1255417...
output:
210379
result:
ok single line: '210379'
Test #38:
score: 0
Accepted
time: 359ms
memory: 94140kb
input:
249996 1670925 231087 0 39527 1983657 0 473410 5370 0 1925481 1720431 0 67352 1896317 0 1504388 1726733 1 267185 1289444 1 1817474 1175113 1 1995074 1664245 0 499013 1967847 0 1648928 1862986 0 1939804 1720616 0 433527 39214 0 1515418 1862505 0 1616861 500050 1 1697588 1794243 0 1208156 242958 1 175...
output:
164113
result:
ok single line: '164113'
Test #39:
score: 0
Accepted
time: 270ms
memory: 47996kb
input:
249952 250574 1778462 0 1826747 837308 1 522919 1819222 0 134196 798730 1 408911 1769945 0 282572 1963935 0 1573844 350523 1 997645 179579 1 545660 1737010 1 1701480 1441783 1 1161949 1833221 1 1551370 59494 0 1532094 214104 0 720104 1906634 0 1336979 258825 1 639637 1880604 0 1678518 3671 0 519444 ...
output:
128606
result:
ok single line: '128606'
Test #40:
score: 0
Accepted
time: 585ms
memory: 94756kb
input:
249962 1570928 1168014 0 1289527 1069368 0 1084465 298630 0 1823246 970084 0 1448051 568213 0 57429 1877382 0 1985663 589872 0 192591 1581816 0 635580 1618658 0 1965199 1744436 0 973848 587670 0 1832568 1364683 0 204794 1526274 0 853401 597947 0 1706385 1388135 0 1394442 748004 0 1927023 1659075 0 1...
output:
23708
result:
ok single line: '23708'
Test #41:
score: 0
Accepted
time: 530ms
memory: 94244kb
input:
249972 884131 132698 0 1506894 1562766 0 777005 1622992 0 1966190 177651 0 367381 942169 0 1988383 6143 0 463050 689081 0 1910856 1788980 0 1840351 978821 0 1209453 1761364 0 434967 1586987 0 1112918 778466 0 1973192 456641 0 1503248 796976 0 1069319 1159757 1 7181 902472 0 923876 1689308 0 1450177 ...
output:
59018
result:
ok single line: '59018'
Test #42:
score: 0
Accepted
time: 177ms
memory: 56628kb
input:
249980 815485 1472579 0 408992 119891 1 613227 536688 0 56071 1821567 1 1798757 1911045 0 477565 1074082 1 934601 373894 0 1789967 302191 0 204776 1469559 1 466130 801703 1 1528053 265224 0 386174 1941600 1 1470080 1248956 0 849523 1043944 0 21679 337669 0 1006660 1824440 0 63376 187202 0 1397095 44...
output:
157728
result:
ok single line: '157728'