请求添加 hack 数据
  • 板块P4192 旅行规划
  • 楼主meyiMessiah
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/6/30 15:58
  • 上次更新2023/11/4 21:09:14
查看原帖
请求添加 hack 数据
67942
meyiMessiah楼主2021/6/30 15:58

本题题解区中 @zero4338 的题解的修改操作每次暴力修改凸包最大值点,其最坏时间复杂度为 O(n)O(n),因此他的最坏的总时间复杂度为 O(n2)O(n^2),然而却通过了本题,请求管理员添加 hack 数据。

数据生成:

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5;
bool flag;
int main(){
	//freopen("input.txt","w",stdout);
	printf("%d\n",maxn);
	for(ri i=1;i<=maxn;++i)printf("%d ",maxn-i+1);
	printf("\n%d\n",maxn);
	for(ri i=1;i<=maxn;++i){
		if(i%3==0)printf("1 %d %d\n",1,maxn);
		else printf("0 %d %d %d\n",1,maxn,(flag^=1)?-maxn:maxn);
	}
	return 0;
}

(顺带一提第一篇和第四篇题解在这组数据下都跑的挺慢的

2021/6/30 15:58
加载中...