QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258406 | #7569. Lines | Loging | WA | 2ms | 13900kb | C++14 | 2.1kb | 2023-11-19 17:48:32 | 2023-11-19 17:48:33 |
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+10.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))==-1)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: 2ms
memory: 13900kb
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: 13884kb
input:
1 1 2 1 2 1 2
output:
2 1 2
result:
ok 3 number(s): "2 1 2"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 13880kb
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:
735 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:
wrong answer 1st numbers differ - expected: '733', found: '735'