QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#184660 | #6734. Click the Circle | bulijiojiodibuliduo# | AC ✓ | 157ms | 4324kb | C++ | 14.8kb | 2023-09-21 02:26:12 | 2023-09-21 02:26:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef double db;
const db EPS = 1e-9;
const db PI = acos(-1.0);
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db distTo(P p) { return (*this-p).abs(); }
db alpha() { return atan2(y, x); }
void read() { cin>>x>>y; }
void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
db abs() { return sqrt(abs2());}
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
P unit() { return *this/abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an){ return {x*cos(an)-y*sin(an),x*sin(an) + y*cos(an)}; }
};
struct L{ //ps[0] -> ps[1]
P ps[2];
P dir_;
P& operator[](int i) { return ps[i]; }
P dir() { return dir_; }
L (P a,P b) {
ps[0]=a;
ps[1]=b;
dir_ = (ps[1]-ps[0]).unit();
}
bool include(P p) { return sign((dir_).det(p - ps[0])) > 0; }
L push(){ // push eps outward
const double eps = 1e-8;
P delta = (ps[1] - ps[0]).rot90().unit() * eps;
return {ps[0] + delta, ps[1] + delta};
}
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
bool chkLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1+a2) != 0;
}
P isLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
P isLL(L l1,L l2){ return isLL(l1[0],l1[1],l2[0],l2[1]); }
bool intersect(db l1,db r1,db l2,db r2){
if(l1>r1) swap(l1,r1); if(l2>r2) swap(l2,r2);
return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
bool isSS(P p1, P p2, P q1, P q2){
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) <= 0;
}
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
bool isMiddle(db a, db m, db b) {
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) {
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
bool onSeg(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
bool onSeg_strict(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
P proj(P p1, P p2, P q) {
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
P reflect(P p1, P p2, P q){
return proj(p1,p2,q) * 2 - q;
}
db nearest(P p1,P p2,P q){
if (p1==p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if(isMiddle(p1,h,p2))
return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
db disSS(P p1, P p2, P q1, P q2){
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
db rad(P p1,P p2){
return atan2l(p1.det(p2),p1.dot(p2));
}
db incircle(P p1, P p2, P p3){
db A = p1.distTo(p2);
db B = p2.distTo(p3);
db C = p3.distTo(p1);
return sqrtl(A*B*C/(A+B+C));
}
//polygon
db area(vector<P> ps){
db ret = 0; rep(i,0,ps.size()) ret += ps[i].det(ps[(i+1)%ps.size()]);
return ret/2;
}
int contain(vector<P> ps, P p){ //2:inside,1:on_seg,0:outside
int n = ps.size(), ret = 0;
rep(i,0,n){
P u=ps[i],v=ps[(i+1)%n];
if(onSeg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y) >0 || cmp(p.y,v.y) <= 0) continue;
ret ^= crossOp(p,u,v) > 0;
}
return ret*2;
}
vector<P> convexHull(vector<P> ps) {
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> convexHullNonStrict(vector<P> ps) {
//caution: need to unique the Ps first
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
qs.resize(k - 1);
return qs;
}
db convexDiameter(vector<P> ps){
int n = ps.size(); if(n <= 1) return 0;
int is = 0, js = 0; rep(k,1,n) is = ps[k]<ps[is]?k:is, js = ps[js] < ps[k]?k:js;
int i = is, j = js;
db ret = ps[i].distTo(ps[j]);
do{
if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j]) >= 0)
(++j)%=n;
else
(++i)%=n;
ret = max(ret,ps[i].distTo(ps[j]));
}while(i!=is || j!=js);
return ret;
}
vector<P> convexCut(const vector<P>&ps, P q1, P q2) {
vector<P> qs;
int n = ps.size();
rep(i,0,n){
P p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = crossOp(q1,q2,p1), d2 = crossOp(q1,q2,p2);
if(d1 >= 0) qs.pb(p1);
if(d1 * d2 < 0) qs.pb(isLL(p1,p2,q1,q2));
}
return qs;
}
//min_dist
db min_dist(vector<P>&ps,int l,int r){
if(r-l<=5){
db ret = 1e100;
rep(i,l,r) rep(j,l,i) ret = min(ret,ps[i].distTo(ps[j]));
return ret;
}
int m = (l+r)>>1;
db ret = min(min_dist(ps,l,m),min_dist(ps,m,r));
vector<P> qs; rep(i,l,r) if(abs(ps[i].x-ps[m].x)<= ret) qs.pb(ps[i]);
sort(qs.begin(), qs.end(),[](P a,P b) -> bool {return a.y<b.y; });
rep(i,1,qs.size()) for(int j=i-1;j>=0&&qs[j].y>=qs[i].y-ret;--j)
ret = min(ret,qs[i].distTo(qs[j]));
return ret;
}
int type(P o1,db r1,P o2,db r2){
db d = o1.distTo(o2);
if(cmp(d,r1+r2) == 1) return 4;
if(cmp(d,r1+r2) == 0) return 3;
if(cmp(d,abs(r1-r2)) == 1) return 2;
if(cmp(d,abs(r1-r2)) == 0) return 1;
return 0;
}
vector<P> isCL(P o,db r,P p1,P p2){
if (cmp(abs((o-p1).det(p2-p1)/p1.distTo(p2)),r)>0) return {};
db x = (p1-o).dot(p2-p1), y = (p2-p1).abs2(), d = x * x - y * ((p1-o).abs2() - r*r);
d = max(d,(db)0.0); P m = p1 - (p2-p1)*(x/y), dr = (p2-p1)*(sqrt(d)/y);
return {m-dr,m+dr}; //along dir: p1->p2
}
vector<P> isCC(P o1, db r1, P o2, db r2) { //need to check whether two circles are the same
db d = o1.distTo(o2);
if (cmp(d, r1 + r2) == 1) return {};
if (cmp(d,abs(r1-r2))==-1) return {};
d = min(d, r1 + r2);
db y = (r1 * r1 + d * d - r2 * r2) / (2 * d), x = sqrt(r1 * r1 - y * y);
P dr = (o2 - o1).unit();
P q1 = o1 + dr * y, q2 = dr.rot90() * x;
return {q1-q2,q1+q2};//along circle 1
}
vector<P> tanCP(P o, db r, P p) {
db x = (p - o).abs2(), d = x - r * r;
if (sign(d) <= 0) return {}; // on circle => no tangent
P q1 = o + (p - o) * (r * r / x);
P q2 = (p - o).rot90() * (r * sqrt(d) / x);
return {q1-q2,q1+q2}; //counter clock-wise
}
// extanCC, intanCC : -r2, tanCP : r2 = 0
vector<pair<P, P>> tanCC(P o1, db r1, P o2, db r2) {
P d = o2 - o1;
db dr = r1 - r2, d2 = d.abs2(), h2 = d2 - dr * dr;
if (sign(d2) == 0|| sign(h2) < 0) return {};
h2 = max(0.0, h2);
vector<pair<P, P>> ret;
for (db sign : {-1, 1}) {
P v = (d * dr + d.rot90() * sqrt(h2) * sign) / d2;
ret.push_back({o1 + v * r1, o2 + v * r2});
}
if (sign(h2) == 0) ret.pop_back();
return ret;
}
db areaCT(db r, P p1, P p2){
vector<P> is = isCL(P(0,0),r,p1,p2);
if(is.empty()) return r*r*rad(p1,p2)/2;
bool b1 = cmp(p1.abs2(),r*r) == 1, b2 = cmp(p2.abs2(), r*r) == 1;
if(b1 && b2){
P md=(is[0]+is[1])/2;
if(sign((p1-md).dot(p2-md)) <= 0)
return r*r*(rad(p1,is[0]) + rad(is[1],p2))/2 + is[0].det(is[1])/2;
else return r*r*rad(p1,p2)/2;
}
if(b1) return (r*r*rad(p1,is[0]) + is[0].det(p2))/2;
if(b2) return (p1.det(is[1]) + r*r*rad(is[1],p2))/2;
return p1.det(p2)/2;
}
bool parallel(L l0, L l1) { return sign( l0.dir().det( l1.dir() ) ) == 0; }
bool sameDir(L l0, L l1) { return parallel(l0, l1) && sign(l0.dir().dot(l1.dir()) ) == 1; }
bool cmp (P a, P b) {
if (a.quad() != b.quad()) {
return a.quad() < b.quad();
} else {
return sign( a.det(b) ) > 0;
}
}
bool operator < (L l0, L l1) {
if (sameDir(l0, l1)) {
return l1.include(l0[0]);
} else {
return cmp( l0.dir(), l1.dir() );
}
}
bool check(L u, L v, L w) {
return w.include(isLL(u,v));
}
vector<P> halfPlaneIS(vector<L> &l) {
sort(l.begin(), l.end());
deque<L> q;
for (int i = 0; i < (int)l.size(); ++i) {
if (i && sameDir(l[i], l[i - 1])) continue;
while (q.size() > 1 && !check(q[q.size() - 2], q[q.size() - 1], l[i])) q.pop_back();
while (q.size() > 1 && !check(q[1], q[0], l[i])) q.pop_front();
q.push_back(l[i]);
}
while (q.size() > 2 && !check(q[q.size() - 2], q[q.size() - 1], q[0])) q.pop_back();
while (q.size() > 2 && !check(q[1], q[0], q[q.size() - 1])) q.pop_front();
vector<P> ret;
for (int i = 0; i < (int)q.size(); ++i) ret.push_back(isLL(q[i], q[(i + 1) % q.size()]));
return ret;
}
P inCenter(P A, P B, P C) {
double a = (B - C).abs(), b = (C - A).abs(), c = (A - B).abs();
return (A * a + B * b + C * c) / (a + b + c);
}
P circumCenter(P a, P b, P c) {
P bb = b - a, cc = c - a;
double db = bb.abs2(), dc = cc.abs2(), d = 2 * bb.det(cc);
return a - P(bb.y * dc - cc.y * db, cc.x * db - bb.x * dc) / d;
}
P othroCenter(P a, P b, P c) {
P ba = b - a, ca = c - a, bc = b - c;
double Y = ba.y * ca.y * bc.y,
A = ca.x * ba.y - ba.x * ca.y,
x0 = (Y + ca.x * ba.y * b.x - ba.x * ca.y * c.x) / A,
y0 = -ba.x * (x0 - c.x) / ba.y + ca.y;
return {x0, y0};
}
int n,r,d;
struct staticc {
P o;
int tl,tr;
staticc() {}
staticc(int x,int y,int tl,int tr):tl(tl),tr(tr) {
o=P(x,y);
}
};
struct rect {
vector<P> p;
};
struct frame {
staticc c1,c2;
rect p;
int tl,tr;
frame() {}
frame(int sx,int sy,int tx,int ty,int u,int v) {
c1=(staticc){sx,sy,u-d,v+d};
c2=(staticc){tx,ty,u-d,v+d};
P s(sx,sy),t(tx,ty);
P dir=((t-s).unit()*r).rot90();
p.p=vector<P>{s-dir,t-dir,t+dir,s+dir};
tl=u-d; tr=v+d;
}
};
struct movingc {
staticc c1,c2;
P s,t,vec;
int tl,tr;
movingc() {}
movingc(int sx,int sy,int tx,int ty,int u,int v) {
c1=staticc(sx,sy,u-d,u);
c2=staticc(tx,ty,v,v+d);
s=P(sx,sy); t=P(tx,ty);
tl=u; tr=v;
vec=(t-s)/(tr-tl);
}
pair<P,P> rest(int xl,int xr) {
xl=max(xl,tl);
xr=min(xr,tr);
assert(xl<=xr);
return mp(s+vec*(xl-tl),s+vec*(xr-tl));
}
};
vector<staticc> cir;
vector<frame> fr;
vector<movingc> mov;
bool stasta(staticc &u, staticc &v) {
return intersect(u.tl,u.tr,v.tl,v.tr)&&type(u.o,r,v.o,r)!=4;
}
bool cirseg(P o,db r,P p1,P p2) {
auto d=isCL(o,r,p1,p2);
for (auto x:d) if (isMiddle(p1,x,p2)) return true;
return false;
}
bool starec(staticc &u,rect &v) {
rep(i,0,SZ(v.p)) {
P p1=v.p[i],p2=v.p[(i+1)%SZ(v.p)];
if (cirseg(u.o,r,p1,p2)) return true;
}
return false;
}
bool recrec(rect &u,rect &v) {
vector<P> p=u.p;
rep(i,0,SZ(v.p)) {
P p1=v.p[i],p2=v.p[(i+1)%SZ(v.p)];
p=convexCut(p,p1,p2);
}
return !p.empty();
}
bool stafr(staticc &u,frame &v) {
if (!intersect(u.tl,u.tr,v.tl,v.tr)) return false;
if (stasta(u,v.c1)||stasta(u,v.c2)) return true;
if (starec(u,v.p)) return true;
return false;
}
bool frfr(frame &u,frame &v) {
if (!intersect(u.tl,u.tr,v.tl,v.tr)) return false;
if (stafr(u.c1,v)||stafr(u.c2,v)||
stafr(v.c1,u)||stafr(v.c2,u)) return true;
if (recrec(u.p,v.p)) return true;
return false;
}
bool stamov(staticc &u,movingc &v) {
if (stasta(u,v.c1)||stasta(u,v.c2)) return true;
if (!intersect(u.tl,u.tr,v.tl,v.tr)) return false;
auto [p1,p2]=v.rest(u.tl,u.tr);
return cmp(nearest(p1,p2,u.o),2*r)!=1;
}
db recseg(rect &u,P p1,P p2) {
vector<P> p=u.p;
if (contain(p,p1)!=0||contain(p,p2)!=0) return 0;
db ans=1e10;
rep(i,0,SZ(p)) {
P q1=p[i],q2=p[(i+1)%SZ(p)];
ans=min(ans,disSS(q1,q2,p1,p2));
}
return ans;
}
bool frmov(frame &u,movingc &v) {
if (stafr(v.c1,u)||stafr(v.c2,u)) return true;
if (stamov(u.c1,v)||stamov(u.c2,v)) return true;
if (!intersect(u.tl,u.tr,v.tl,v.tr)) return false;
auto [p1,p2]=v.rest(u.tl,u.tr);
return cmp(recseg(u.p,p1,p2),r)!=1;
}
bool movmov(movingc &u,movingc &v) {
if (stamov(u.c1,v)||stamov(u.c2,v)||
stamov(v.c1,u)||stamov(v.c2,u)) return true;
if (!intersect(u.tl,u.tr,v.tl,v.tr)) return false;
auto [p1,p2]=u.rest(v.tl,v.tr);
auto [q1,q2]=v.rest(u.tl,u.tr);
return cmp(nearest(q1-p1,q2-p2,P(0,0)),2*r)!=1;
}
int main() {
scanf("%d%d%d",&n,&r,&d);
rep(i,0,n) {
int ty;
scanf("%d",&ty);
if (ty==1) {
int cx,cy,t;
scanf("%d%d%d",&cx,&cy,&t);
cir.pb(staticc(cx,cy,t-d,t+d));
} else {
int sx,sy,tx,ty,u,v;
scanf("%d%d%d%d%d%d",&sx,&sy,&tx,&ty,&u,&v);
if (sx==tx&&sy==ty) {
cir.pb(staticc(sx,sy,u-d,v+d));
cir.pb(staticc(sx,sy,u-d,v+d));
} else {
mov.pb(movingc(sx,sy,tx,ty,u,v));
fr.pb(frame(sx,sy,tx,ty,u,v));
}
}
}
int ans=0;
rep(i,0,SZ(cir)) rep(j,i+1,SZ(cir)) {
auto u=cir[i];
auto v=cir[j];
ans+=stasta(u,v);
}
fprintf(stderr,"%d\n",ans);
rep(i,0,SZ(cir)) rep(j,0,SZ(fr)) {
auto u=cir[i];
auto v=fr[j];
ans+=stafr(u,v);
}
fprintf(stderr,"%d\n",ans);
rep(i,0,SZ(fr)) rep(j,i+1,SZ(fr)) {
auto u=fr[i];
auto v=fr[j];
ans+=frfr(u,v);
}
fprintf(stderr,"%d\n",ans);
rep(i,0,SZ(cir)) rep(j,0,SZ(mov)) {
auto u=cir[i];
auto v=mov[j];
ans+=stamov(u,v);
}
fprintf(stderr,"%d\n",ans);
rep(i,0,SZ(fr)) rep(j,0,SZ(mov)) {
auto u=fr[i];
auto v=mov[j];
ans+=frmov(u,v);
}
fprintf(stderr,"%d\n",ans);
rep(i,0,SZ(mov)) rep(j,i+1,SZ(mov)) {
auto u=mov[i];
auto v=mov[j];
ans+=movmov(u,v);
}
printf("%d\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4104kb
input:
2 1 1 1 1 1 2 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 1 1 1 1 1 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2 1 1 1 3 3 2 2 5 5 5 1 2 4
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 1 1 2 1 1 1 5 2 4 2 5 5 5 1 2 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 1 1 2 10 1 10 20 2 4 2 1 10 20 10 2 4
output:
6
result:
ok 1 number(s): "6"
Test #6:
score: 0
Accepted
time: 42ms
memory: 4076kb
input:
1000 8 4 1 8323 2820 943 1 8246 2850 944 1 8177 2880 941 1 8154 2866 944 2 8325 8146 2865 2846 943 944 1 8349 2891 939 2 8176 8344 2888 2692 940 945 1 8191 2732 945 1 8144 2668 945 2 8182 8191 2889 2844 939 940 1 8173 2687 941 1 8241 2870 945 2 8266 8344 2910 2667 942 943 1 8169 2863 939 1 8349 2921...
output:
22721
result:
ok 1 number(s): "22721"
Test #7:
score: 0
Accepted
time: 39ms
memory: 4056kb
input:
1000 35 8 2 1037 1102 9971 9940 531 534 1 301 9951 548 1 944 9962 529 1 592 9968 537 1 262 9949 531 1 312 9971 553 1 1139 9938 550 2 325 747 9967 9970 539 544 1 810 9941 536 2 906 486 9956 9953 550 552 1 1121 9940 543 2 515 1199 9965 9953 548 552 2 537 926 9972 9949 538 547 1 1356 9967 550 1 332 996...
output:
34559
result:
ok 1 number(s): "34559"
Test #8:
score: 0
Accepted
time: 43ms
memory: 4324kb
input:
1000 472 14 1 3783 7912 938 1 3307 7801 773 1 4605 7852 592 1 2999 7886 644 1 5308 7914 865 1 4978 7842 611 2 3205 5292 7915 7915 724 835 1 6173 7919 846 2 3130 4833 7921 7853 893 906 1 3449 7854 938 2 4951 3238 7824 7897 720 874 2 4842 5378 7906 7913 683 853 2 4991 4467 7906 7830 580 779 2 5782 615...
output:
103238
result:
ok 1 number(s): "103238"
Test #9:
score: 0
Accepted
time: 63ms
memory: 4052kb
input:
1000 4 51 2 6933 7307 7777 7798 450 456 2 6444 6705 7787 7794 447 460 1 7192 7784 464 2 7865 6422 7791 7797 451 460 1 7366 7794 461 2 7364 6214 7785 7782 449 454 2 7378 7099 7801 7798 450 461 2 7961 6794 7784 7788 448 449 2 6510 7007 7787 7797 453 458 1 6517 7786 446 2 6725 7216 7797 7788 451 452 2 ...
output:
36558
result:
ok 1 number(s): "36558"
Test #10:
score: 0
Accepted
time: 44ms
memory: 4240kb
input:
1000 27 6 2 3760 3746 1523 1749 339 366 2 3738 3746 1688 1609 334 356 1 3754 1559 349 1 3761 1551 347 2 3746 3755 1667 1528 338 340 2 3754 3749 1565 1664 331 356 2 3746 3759 1653 1674 357 362 2 3753 3739 1741 1625 346 359 2 3763 3747 1701 1738 340 343 2 3742 3754 1695 1759 361 366 2 3742 3752 1654 1...
output:
36245
result:
ok 1 number(s): "36245"
Test #11:
score: 0
Accepted
time: 69ms
memory: 4080kb
input:
1000 78 150 1 6600 430 535 1 6589 476 532 2 6596 6596 430 489 530 533 2 6598 6601 469 470 529 531 1 6597 495 534 1 6597 474 533 2 6592 6599 467 465 536 538 2 6600 6596 460 484 535 537 1 6587 461 529 2 6596 6596 431 485 532 533 1 6597 465 538 2 6591 6597 429 465 530 534 1 6598 439 533 2 6596 6588 458...
output:
92999
result:
ok 1 number(s): "92999"
Test #12:
score: 0
Accepted
time: 157ms
memory: 4036kb
input:
1000 19 854 1 4584 7521 143 1 4587 7497 142 2 4587 4582 7516 7363 145 147 2 4591 4585 7360 7370 143 147 2 4582 4589 7491 7418 145 147 1 4592 7366 145 2 4587 4585 7402 7375 142 143 2 4584 4585 7392 7516 145 147 2 4584 4587 7383 7502 142 147 1 4583 7462 145 1 4592 7461 146 1 4588 7409 142 2 4591 4590 ...
output:
163887
result:
ok 1 number(s): "163887"
Test #13:
score: 0
Accepted
time: 139ms
memory: 4088kb
input:
1000 38 834 2 727 740 7904 8009 721 901 2 771 686 7753 7896 707 714 2 790 766 7801 7864 877 919 1 790 7902 874 2 709 686 7990 7998 739 760 1 666 7941 849 2 677 726 8009 7939 810 820 2 679 686 7896 7935 810 923 2 747 718 8018 7963 700 786 1 719 7987 825 1 697 7975 931 1 764 7794 847 1 659 7813 813 1 ...
output:
203301
result:
ok 1 number(s): "203301"
Test #14:
score: 0
Accepted
time: 38ms
memory: 3984kb
input:
1000 767 32 2 615 605 4677 4694 404 408 1 620 4687 421 1 617 4681 452 1 621 4687 436 2 609 608 4698 4678 404 433 2 603 620 4690 4680 391 419 2 604 609 4682 4678 405 428 1 615 4678 443 2 615 611 4678 4698 402 413 1 614 4692 450 2 601 616 4695 4692 441 442 1 614 4674 401 1 617 4697 420 1 606 4698 423 ...
output:
104679
result:
ok 1 number(s): "104679"
Test #15:
score: 0
Accepted
time: 32ms
memory: 4288kb
input:
1000 68 9 1 4226 6175 121 2 4232 4221 5792 5879 82 102 1 4226 6152 69 1 4226 5910 69 2 4238 4242 6314 6215 70 74 1 4233 6208 149 1 4247 5765 162 2 4237 4221 5787 5877 180 192 1 4223 5966 148 1 4221 5925 111 2 4241 4245 6105 6069 173 203 1 4234 6275 108 1 4230 5952 166 1 4247 5925 214 1 4220 6288 192...
output:
43227
result:
ok 1 number(s): "43227"
Test #16:
score: 0
Accepted
time: 139ms
memory: 4296kb
input:
1000 20 500 2 9234 9242 4563 4578 972 976 2 9230 9142 4582 4551 972 973 1 9207 4564 971 1 9246 4561 973 2 9228 9253 4564 4571 976 977 1 9132 4566 973 2 9207 9273 4564 4582 970 982 2 9182 9172 4552 4583 965 970 2 9241 9248 4561 4564 965 966 1 9160 4570 978 1 9171 4573 978 1 9288 4564 977 2 9124 9209 ...
output:
168341
result:
ok 1 number(s): "168341"
Test #17:
score: 0
Accepted
time: 54ms
memory: 3996kb
input:
1000 479 93 2 3917 4659 8054 8309 907 919 1 3652 8108 917 1 3807 8421 889 1 3809 7956 918 2 5455 6444 8146 7993 888 897 1 3919 8428 896 1 5806 8417 904 1 5003 8284 908 1 4433 8111 900 2 4758 5119 8171 8370 893 917 1 5167 8085 909 2 5355 4401 8243 8214 894 902 2 4998 6113 8049 7961 901 905 2 6438 588...
output:
130628
result:
ok 1 number(s): "130628"
Test #18:
score: 0
Accepted
time: 62ms
memory: 3976kb
input:
1000 9 64 2 4598 4157 749 771 946 951 2 3869 4053 744 756 946 957 1 3637 785 963 2 4680 4023 760 797 949 950 2 3674 3955 743 759 949 951 1 4442 794 951 2 4336 4099 806 743 946 962 1 4544 787 962 2 4316 4548 743 802 956 963 1 3582 768 949 1 4230 794 955 2 4477 4446 778 780 957 958 2 3758 4306 751 781...
output:
35598
result:
ok 1 number(s): "35598"
Test #19:
score: 0
Accepted
time: 47ms
memory: 4260kb
input:
1000 57 27 1 7434 3356 642 2 7427 7433 3355 3354 669 684 2 7432 7435 3353 3354 683 778 1 7424 3356 772 2 7434 7421 3356 3351 727 803 2 7432 7420 3355 3352 672 695 2 7426 7421 3353 3354 630 656 2 7425 7420 3352 3355 696 701 1 7428 3352 720 1 7429 3355 692 1 7433 3353 714 1 7430 3355 838 2 7432 7420 3...
output:
61871
result:
ok 1 number(s): "61871"
Test #20:
score: 0
Accepted
time: 81ms
memory: 4244kb
input:
1000 883 463 1 2380 6779 801 2 1342 1303 6814 6780 800 801 2 263 1224 6797 6792 801 803 2 623 427 6787 6793 801 803 2 398 2034 6801 6790 802 803 1 1521 6782 800 1 1090 6807 803 1 575 6806 799 2 998 1435 6782 6788 801 803 1 811 6799 800 2 1509 1567 6783 6779 799 800 1 1156 6812 800 1 294 6802 800 1 1...
output:
522826
result:
ok 1 number(s): "522826"
Test #21:
score: 0
Accepted
time: 151ms
memory: 4308kb
input:
1000 1 430 2 9469 9548 8535 8853 127 180 1 9510 9271 108 1 9417 9255 118 1 9603 9094 127 1 9416 8441 120 2 9591 9501 9100 9100 147 198 2 9413 9551 8606 8240 216 223 2 9506 9525 8715 9157 80 152 1 9559 8977 42 1 9552 9286 54 2 9555 9551 8424 9279 37 131 1 9376 9085 61 2 9488 9543 9140 9374 87 222 2 9...
output:
59834
result:
ok 1 number(s): "59834"
Test #22:
score: 0
Accepted
time: 32ms
memory: 3968kb
input:
1000 49 3 2 8881 8913 1885 2159 225 239 1 8883 1980 245 2 8908 8883 2082 2199 223 254 2 8903 8905 2170 2048 229 247 1 8882 1944 225 1 8910 1844 247 2 8887 8902 2034 2080 232 233 1 8887 2082 250 1 8901 1908 251 2 8899 8884 1884 2112 242 245 1 8889 1914 254 1 8899 2188 250 2 8908 8881 2071 2019 239 24...
output:
24042
result:
ok 1 number(s): "24042"
Test #23:
score: 0
Accepted
time: 121ms
memory: 3984kb
input:
1000 51 968 1 3531 6961 345 1 4472 7149 357 1 2691 6615 359 2 3325 4548 7314 6828 356 358 2 4801 3905 6987 6647 358 372 1 4974 6876 366 1 4527 6792 344 2 3363 3335 7054 7147 359 365 1 2922 6705 375 1 4487 7293 355 2 3236 4914 6926 6782 346 374 1 4463 6740 369 1 2796 6833 361 1 3969 6830 358 1 4665 7...
output:
274214
result:
ok 1 number(s): "274214"
Test #24:
score: 0
Accepted
time: 50ms
memory: 4236kb
input:
1000 1 10 2 5234 5378 7146 7016 658 806 2 3852 5355 6863 6990 837 883 2 3953 3596 7007 6909 701 756 1 6504 6967 920 2 4033 5760 6873 7090 674 869 2 4163 4267 7178 6938 864 912 1 3622 6948 938 1 5798 7146 824 1 4829 7126 786 1 4400 6989 775 1 4738 6933 854 2 4230 5240 6863 7148 711 796 1 3987 7172 84...
output:
15333
result:
ok 1 number(s): "15333"
Test #25:
score: 0
Accepted
time: 49ms
memory: 4084kb
input:
1000 614 50 2 2448 2538 7136 7095 541 552 1 2348 7052 565 1 2498 7085 554 2 2313 2444 7132 7152 552 564 1 2300 7021 560 1 2289 7066 553 2 2572 2547 7122 7067 551 563 2 2473 2462 7054 7062 556 563 1 2290 7046 553 2 2397 2493 7134 7053 547 550 1 2312 7049 551 2 2595 2448 7085 7113 549 557 2 2432 2314 ...
output:
133247
result:
ok 1 number(s): "133247"