QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258416 | #7569. Lines | Loging | WA | 2ms | 15904kb | C++14 | 2.2kb | 2023-11-19 17:54:11 | 2023-11-19 17:54:13 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 300005
#define int long long
struct node{
int id,num;
double get_val(double x){
return 1.0*x*id+num;
}
};
struct Cp{
long long x,y;
bool operator <(const Cp &_)const{
// return 1.0*x/y<1.0*_.x/_.y;
return (__int128)x*_.y<(__int128)_.x*y;
}
};
Cp Get_Pointx(node a,node b){
return (Cp){b.num-a.num,a.id-b.id};
}
#define eps 1e-8
int sign(double x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
int n;
double D[M<<3];
int sz_val;
struct solve_automation{
int val[M];
int sz,p;
node stk[M];
void Init(){
p=1;sz=0;
for(int i=0;i<=n;i++){
node now=(node){i,val[i]};
while(sz>1&&Get_Pointx(stk[sz-1],now)<Get_Pointx(stk[sz-1],stk[sz]))sz--;
stk[++sz]=now;
}
for(int i=1;i<sz;i++){
Cp tmp=Get_Pointx(stk[i],stk[i+1]);
double x=1.0*tmp.x/tmp.y;
D[++sz_val]=x;
// D[++sz_val]=x-10.0*eps;
// D[++sz_val]=x-20.0*eps;
// D[++sz_val]=x+10.0*eps;
// D[++sz_val]=x+20.0*eps;
// D[++sz_val]=x+2;
// D[++sz_val]=x-2;
// printf("x=%lld\n",x);
}
// for(int i=1;i<=sz;i++)printf("(%d %d) ",stk[i].id,stk[i].num);puts("");
}
int Get_val(double x){
while(p<sz&&sign(stk[p].get_val(x)-stk[p+1].get_val(x))<=0)p++;
// if(p<sz&&sign(stk[p].get_val(x)-stk[p+1].get_val(x))==0)return -1;
return stk[p].id;
}
}A,B,C;
bool mark[M*3];
int Ans[M*3],sz;
signed main(){
// freopen("data.in","r",stdin);
// freopen("AC.out","w",stdout);
scanf("%lld",&n);
for(int i=0;i<=n;i++)scanf("%lld",&A.val[i]);
for(int i=0;i<=n;i++)scanf("%lld",&B.val[i]);
for(int i=0;i<=n;i++)scanf("%lld",&C.val[i]);
A.Init();B.Init();C.Init();
D[++sz_val]=-2e9;
D[++sz_val]=2e9;
sort(D+1,D+sz_val+1);
sz_val=unique(D+1,D+sz_val+1)-D-1;
// for(int i=1;i<=sz_val;i++)printf("%lf ",D[i]);puts("");
// puts("Initok");
for(int i=1;i<=sz_val;i++){
int x=A.Get_val(D[i]),y=B.Get_val(D[i]),z=C.Get_val(D[i]);
// printf("%lf %lld %lld %lld\n",D[i],x,y,z);
if(x==-1||y==-1||z==-1)continue;
mark[x+y+z]=true;
}
for(int i=0;i<=3*n;i++)if(!mark[i])Ans[++sz]=i;
printf("%lld\n",sz);
for(int i=1;i<=sz;i++)printf("%lld ",Ans[i]);puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15844kb
input:
3 3 1 8 7 9 1 3 1 5 1 1 6
output:
5 1 3 4 7 8
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 13864kb
input:
1 1 2 1 2 1 2
output:
2 1 2
result:
ok 3 number(s): "2 1 2"
Test #3:
score: 0
Accepted
time: 2ms
memory: 15840kb
input:
252 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 1...
output:
733 4 5 7 9 10 11 12 14 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 10...
result:
ok 734 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 15904kb
input:
96 75475634 804928248 476927808 284875072 503158867 627937890 322595515 786026685 645468307 669240390 939887597 588586447 973764525 521365644 710156469 985188306 860350786 11308832 784695957 770562147 208427221 35937909 67590963 726478310 475357775 255361535 135993561 166967811 46718075 851555000 70...
output:
272 2 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 39 40 42 43 44 45 46 47 48 49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106...
result:
ok 273 numbers
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 13852kb
input:
237 374288891 535590429 751244358 124321145 232930851 266089174 543529670 773363571 319728747 580543238 582720391 468188689 490702144 598813561 138628383 284660056 733781508 155605777 931759705 245485733 723534730 257812292 794937524 596788519 188451996 981010588 14483682 59267682 959461493 32106527...
output:
686 2 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 44 45 46 47 48 49 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 106 107 108 ...
result:
wrong answer 1st numbers differ - expected: '685', found: '686'