QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258360#7569. LinesLogingWA 67ms20100kbC++142.0kb2023-11-19 17:29:302023-11-19 17:29:31

Judging History

你现在查看的是最新测评结果

  • [2023-11-19 17:29:31]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:20100kb
  • [2023-11-19 17:29:30]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using namespace std;
#define M 300005
#define int long long
struct node{
	int id,num;
	__int128 get_val(long long x){
		return (__int128)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};
}
int n;
long long 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]);
			long long x=tmp.x/tmp.y;
			D[++sz_val]=x;
			D[++sz_val]=x-1;
			D[++sz_val]=x+1;
			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(long long x){
		while(p<sz&&stk[p].get_val(x)<stk[p+1].get_val(x))p++;
		if(p<sz&&stk[p].get_val(x)==stk[p+1].get_val(x))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("%lld ",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]);
		if(x==-1||y==-1||z==-1)continue;
//		printf("%lld %d %d %d\n",D[i],x,y,z);
		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: 13944kb

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: 2ms
memory: 13880kb

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: 0ms
memory: 13892kb

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: 15888kb

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: 0
Accepted
time: 0ms
memory: 13896kb

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:

685
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:

ok 686 numbers

Test #6:

score: -100
Wrong Answer
time: 67ms
memory: 20100kb

input:

213081
673102149 561219907 730593611 814024114 812959730 314305867 469496529 350635050 699021890 342102981 815487777 787982418 857896659 526518374 421876106 438907614 902179526 449645826 783856158 865633510 238642240 774653971 962475573 467098727 196513513 561435449 333165290 951567552 726980720 645...

output:

639195
3 6 7 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 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 10...

result:

wrong answer 1st numbers differ - expected: '639188', found: '639195'