QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259144#7569. LinesLogingWA 0ms3064kbC++141.1kb2023-11-20 17:16:472023-11-20 17:16:48

Judging History

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

  • [2023-11-20 17:16:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3064kb
  • [2023-11-20 17:16:47]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<algorithm>
#define M 300005
#define int64 long long
using namespace std;
struct node{
	int x,y;
	node operator -(const node &_)const{
		return (node){x-_.x,y-_.y};
	}
};
bool mark[M*3];
int val[M];
vector<int>Ans;
vector<node>stk,All;
long long cross(node a,node b){
	return a.x*b.y-a.y*b.x;
}
bool cmp(node x,node y){
	return cross(x,y)<0;
}
int main(){
	int n;
	scanf("%d",&n);
	int T=3;
	while(T--){
		stk.clear();
		for(int i=0;i<=n;i++){
			int x;
			scanf("%d",&x);
			node now=(node){i,x};
			while((int)stk.size()>1&&cross(stk[stk.size()-1]-stk[stk.size()-2],now-stk[stk.size()-2])>=0)stk.pop_back();
			stk.push_back(now);
		}
		All.push_back(stk[0]);
		for(int i=1;i<(int)stk.size();i++)All.push_back(stk[i]-stk[i-1]);
	}
	sort(All.begin(),All.end(),cmp);
	int res=0;
	for(int i=0;i<(int)All.size();i++){
		res+=All[i].x;
		if(i==(int)All.size()-1||cross(All[i],All[i+1])!=0)mark[res]=true;
	}
	for(int i=0;i<=3*n;i++)if(!mark[i])Ans.push_back(i);
	printf("%d\n",(int)Ans.size());
	for(int i=0;i<(int)Ans.size();i++)printf("%d ",Ans[i]);puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3064kb

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

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

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:

665
7 15 16 17 18 19 22 24 30 32 34 36 37 39 42 44 45 48 50 52 53 54 55 56 57 58 60 62 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 100 101 102 103 104 105 106 108 109 111 112 113 114 115 116 117 118 119 121 122 124 125 126 127 128 130 131 ...

result:

wrong answer 1st numbers differ - expected: '733', found: '665'