QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235900#7569. LinesqwqwfWA 70ms25264kbC++142.2kb2023-11-03 12:41:502023-11-03 12:41:50

Judging History

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

  • [2023-11-03 12:41:50]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:25264kb
  • [2023-11-03 12:41:50]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
using namespace std;
const int N=4e5+20,M=1e6+20,mod=998244353;
struct Node{ll x,y;}stk[N],v1[N],v2[N],s1[N],s2[N],p[N],a[N],b[N],c[N];int top;
inline Node operator -(Node a,Node b){return (Node){a.x-b.x,a.y-b.y};}
inline Node operator +(Node a,Node b){return (Node){a.x+b.x,a.y+b.y};}
inline ll operator *(Node a,Node b){return a.x*b.y-a.y*b.x;}
struct Vec{ll x,y;}vec[N];
inline ll pw(ll x){return x*x;}
inline ll lens(Node a){return pw(a.x)+pw(a.y);}
inline ll Cross(Vec a,Vec b){return a.x*b.y-a.y*b.x;}
inline ll Side(Node a,Node b,Node c){Vec v1=(Vec){b.x-a.x,b.y-a.y};Vec v2=(Vec){c.x-b.x,c.y-b.y};return Cross(v1,v2);}
inline bool cmp(Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline bool cmp2(Node a,Node b){return a*b<0;}
void Andrew(Node* p,int& n){
	memset(stk,0,sizeof(stk));
	stk[1]=p[1];stk[2]=p[2];top=2;
	for(int i=3;i<=n;i++){
		while(top>1&&Side(stk[top-1],stk[top],p[i])>=0) top--;
		stk[++top]=p[i];
	}
	n=top;
	for(int i=1;i<=n;i++) p[i]=stk[i];
}
int cnt;
void Minkowski(Node* s1,Node* s2,Node* s3,int &n,int m,int k){
	vector<Node> v,res;v.clear();res.clear();
	for(int i=2;i<=n;i++) v.pb(s1[i]-s1[i-1]);
	for(int i=2;i<=m;i++) v.pb(s2[i]-s2[i-1]);
	for(int i=2;i<=k;i++) v.pb(s3[i]-s3[i-1]);
	sort(v.begin(),v.end(),cmp2);
	res.pb(s1[1]+s2[1]+s3[1]);
	for(auto u:v) res.pb(res.back()+u);
	n=res.size();
	for(int i=1;i<=n;i++) s1[i]=res[i-1];
}
int n,vis[N];
int len[3];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;n++;
	len[0]=len[1]=len[2]=n;
	for(int i=1;i<=n;i++) a[i].x=i-1,cin>>a[i].y;
	for(int i=1;i<=n;i++) b[i].x=i-1,cin>>b[i].y;
	for(int i=1;i<=n;i++) c[i].x=i-1,cin>>c[i].y;
	Andrew(a,len[0]);Andrew(b,len[1]);Andrew(c,len[2]);
	Minkowski(a,b,c,len[0],len[1],len[2]);
	Andrew(a,len[0]);
	int cnt=0;
	for(int i=1;i<=len[0];i++) if(!vis[a[i].x]) cnt++,vis[a[i].x]=1;
	cout<<3*(n-1)+1-cnt<<'\n';
	for(int i=0;i<=3*(n-1);i++) if(!vis[i]) cout<<i<<' ';
	return 0;
}
/*
3
3 1 8 7
9 1 3 1
5 1 1 6
1
1 2
1 2
1 2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 19852kb

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: 4ms
memory: 18424kb

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: 3ms
memory: 19708kb

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

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

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: 70ms
memory: 25264kb

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:

639188
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 399989th numbers differ - expected: '400020', found: '400021'