QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246541#7419. Jiry MatchingsqLWA 227ms54716kbC++148.3kb2023-11-10 21:55:522023-11-10 21:55:53

Judging History

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

  • [2024-06-05 15:26:21]
  • hack成功,自动添加数据
  • (/hack/645)
  • [2023-11-10 21:55:53]
  • 评测
  • 测评结果:WA
  • 用时:227ms
  • 内存:54716kb
  • [2023-11-10 21:55:52]
  • 提交

answer

#include<cstdio>
#include<type_traits>
#include<initializer_list>
/**
 * Author: qL
 * Version: 0x01
 * Note:
 * 	Flush::Fast_Input_Flush_Safer can't work well now.
*/
namespace Default_Source{
	namespace IO{
		namespace Flush{
			struct Input_Flush_Base{char getc(){return getchar();}};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Base:Input_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				Fast_Input_Flush_Base(){std::fread(buf,1,BUFSIZE,stdin);}
				char getc(){return *cur++;}
			};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Safer:Fast_Input_Flush_Base<BUFSIZE>{
			protected:
				using Fast_Input_Flush_Base<BUFSIZE>::buf;
				using Fast_Input_Flush_Base<BUFSIZE>::cur;
				char *nil=buf;
				void reload(){nil=(cur=buf)+std::fread(buf,1,BUFSIZE,stdin);}
			public:
				Fast_Input_Flush_Safer(){reload();}
				char getc(){return (cur==nil&&(reload(),true)),*cur++;}
			};
			struct Output_Flush_Base{void putc(char ch){putchar(ch);}};
			template<std::size_t BUFSIZE>
			class Fast_Output_Flush_Base:Output_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				~Fast_Output_Flush_Base(){std::fwrite(buf,1,cur-buf,stdout);}
				void putc(char ch){*cur++=ch;}
			};
		}
		template<typename _Input_Flush=Flush::Input_Flush_Base>
		class Fast_InStream{
		private:
			static_assert(std::is_base_of<Flush::Input_Flush_Base,_Input_Flush>::value);
			static _Input_Flush Input;
			int Ch;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type read(_Tp &x){
				x=0;Ch=Input.getc();
				for(;Ch<'0'||Ch>'9';Ch=Input.getc());
				for(;Ch>='0'&&Ch<='9';Ch=Input.getc()) x=x*10+(Ch&15);
				return;
			}
			void read(char *str){
				char *ptr=str;
				while((*str=Input.getc())==' '||*str=='\n');
				while((*++str=Input.getc())!=' '&&*str!='\n');
				*str='\0';
			}
			template<typename ...Args>
			void read(Args &&...args){void(List_Out{(read(args),0)...});}
		};
		template<typename _Input_Flush>
		_Input_Flush Fast_InStream<_Input_Flush>::Input;
		template<typename _Output_Flush=Flush::Output_Flush_Base>
		class Fast_OutStream{
		private:
			static_assert(std::is_base_of<Flush::Output_Flush_Base,_Output_Flush>::value);
			static _Output_Flush Output;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type write(_Tp x){
				static char sta[114];
				int top=0;
				do sta[top++]=(x%10)|48,x/=10;
				while(x);
				while(top) Output.putc(sta[--top]);
			}
			void write(char Ch){Output.putc(Ch);}
			template<typename ...Args>
			void write(Args &&...args){void(List_Out{(write(args),0)...});}
			template<typename ...Args>
			void writeln(Args &&...args){write(args...),Output.putc('\n');}
		};
		template<typename _Output_Flush>
		_Output_Flush Fast_OutStream<_Output_Flush>::Output;
	}
}
using namespace Default_Source;
/**
 * 考虑先写个暴力版本。
 * 我们定义 f[u][k] 表示 u 的子树中匹配 k 对,u 随意匹配的答案。
 * 然后定义 g[u][k] 表示 u 的子树中匹配 k 对,u 不能匹配的答案。
 * 转移不是很好说,我们抽象为卷积:f[i]=max(i=j+k){g[j]+h[k]}
 * 那么 g[u] 就是直接把儿子的 f 卷起来,f[u]……好像也是卷起来?
 * u 跟儿子匹配怎么考虑?枚举一下这个儿子?
 * 不是很合理,不妨先卷一个 h 出来,然后 f[u][i]=max{h[i-1]+edge[u][v]}。
 * 是这样的。
 * 那么由于这是个树上匹配,所以是二分图,然后能费用流,于是……
 * 闵可夫斯基和是吧,直接做 O(n^2)。
 * 之后的优化貌似是 tricked,先写一写。
 * 天真了天真了,暴力没那么好写。
 * 其他部分用 f 卷,其中某个儿子用 g 卷得到最优,于是我们可以使用在 CF1442D Sum 得到的分治 trick 处理儿子!
 * HD!/bx/bx/bx(伏笔,来袭!)
 * 现在需要重链剖分优化,个人认为这是个很神奇的方案。
 * 我们对于轻儿子,可以直接分治跑出来,过得去。
 * 然后并进一条重链,考虑怎么弄。
 * 事实上一条重链相当于是一个序列,序列的每个位置下面挂了些什么怪力乱神。
 * 哦我懂了。
 * 然而我们的合并很恐怖,需要分成四大类进行讨论。
 * 我谔谔。
 * 等下哈,好像他们的做法和我的不是很一样。
 * 问题不大,自信即颠峰。
 * 等下上面那个轻儿子分治是 n^2 的……
 * 呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃
 * 重写吧垃圾 lq
*/
#include<string>
using ll=long long;
constexpr ll llInf=0x3f3f3f3f3f3f3f3f;
template<typename T>
const T &max(const T &lhs,const T &rhs){return lhs<rhs?rhs:lhs;}
using Poly=std::basic_string<ll>;
Poly times(const Poly &g,const Poly &h){
	if(h.empty()) return g;
	else if(g.empty()) return h;
	Poly f;f.resize(g.size()+h.size()-1),f[0]=g[0]+h[0];
	for(unsigned k=1,i=1,j=1;k!=f.size();++k)
		if(i==g.size()) f[k]=f[k-1]+h[j]-h[j-1],++j;
		else if(j==h.size()) f[k]=f[k-1]+g[i]-g[i-1],++i;
		else if(g[i]-g[i-1]>h[j]-h[j-1]) f[k]=f[k-1]+g[i]-g[i-1],++i;
		else f[k]=f[k-1]+h[j]-h[j-1],++j;
	return f;
}
Poly plus(const Poly &g,const int &v){
	Poly f;f.resize(g.size()+1),f[0]=g[0],f.back()=g.back()+v;
	for(unsigned k=1;k!=g.size();++k) f[k]=max(g[k],g[k-1]+v);
	return f;
}
Poly merge(const Poly &g,const Poly &h){
	Poly f;f.resize(max(g.size(),h.size()));
	for(unsigned k=0;k!=f.size();++k)
		f[k]=max(k<g.size()?g[k]:-llInf,k<h.size()?h[k]:-llInf);
	return f;
}
template<typename ...Args>
Poly merge(const Poly &f,const Args &...args){return merge(f,merge(args...));}
constexpr int N=2e5;
struct Val{Poly f,g;};
Val dot(const Val &g,const Val &h){
	Val f={};
	f.f=merge(times(g.f,h.g),times(g.g,h.f),f.g=times(g.g,h.g));
	return f;
}
Val p[N+1];
int n;
struct edge{int ver,cost;};
std::basic_string<edge> G[N+1];
int siz[N+1],dep[N+1],fa[N+1],son[N+1],top[N+1],val[N+1];
void dfs(int u){
	siz[u]=1,dep[u]=dep[fa[u]]+1;
	for(edge e:G[u]) if(e.ver!=fa[u])
		fa[e.ver]=u,dfs(e.ver),siz[u]+=siz[e.ver],
		val[e.ver]=e.cost,siz[son[u]]<siz[e.ver]&&(son[u]=e.ver);
}
int seq[N+1];
Val Light_Divide(int l,int r){
	if(l==r) return {plus(p[seq[l]].g,val[seq[l]]),p[seq[r]].f};
	int mid=(l+r)>>1;
	return dot(Light_Divide(l,mid),Light_Divide(mid+1,r));
}
struct Node{Poly q[2][2];};
/**
 * 理清思路:
 * 0 表示任意,1 表示不能。
 * 准则是:
 * 	- 任意的转移不成限制。
 * 	- 正常情况使用 times 卷。
 * 	- 不能劣于任意,一般不考虑。
 * 	- 考虑不能,则要求两边能凑出,此时用 plus 卷。
 * 	- 对于 plus 卷,0/1 限制了的不需要再用两边的限制。
*/
Node dot(const Node &g,const Node &h,int val,bool lhs,bool rhs){
	Node f={};
	f.q[1][1]=times(g.q[1][0],h.q[0][1]);
	if(lhs&&rhs) f.q[1][1]=merge(f.q[1][1],times(plus(g.q[1][1],val),h.q[1][1]));
	f.q[0][1]=merge(times(g.q[0][0],h.q[0][1]),f.q[1][1]),f.q[1][0]=merge(times(g.q[1][0],h.q[0][0]),f.q[1][1]);
	if(lhs) f.q[0][1]=merge(f.q[0][1],times(plus(g.q[0][1],val),h.q[1][1]));
	if(rhs) f.q[1][0]=merge(f.q[1][0],times(plus(g.q[1][1],val),h.q[1][0]));
	f.q[0][0]=merge(times(g.q[0][0],h.q[0][0]),times(plus(g.q[0][1],val),h.q[1][0]),f.q[0][1],f.q[1][0]);
	return f;
}
Node Heavy_Divide(int l,int r){
	if(l==r) return {p[seq[l]].f,p[seq[l]].g,p[seq[r]].g,p[seq[r]].g};
	int mid=(l+r)>>1;
	return dot(Heavy_Divide(l,mid),Heavy_Divide(mid+1,r),val[seq[mid+1]],l!=mid,mid+1!=r);
}
void dfs(int u,int tp){
	p[u]={{0},{0}};
	top[u]=tp,son[u]&&(dfs(son[u],tp),true);
	for(edge e:G[u]) if(!top[e.ver]) dfs(e.ver,e.ver);
	int tot=0;
	for(edge e:G[u]) if(e.ver!=fa[u]&&e.ver!=son[u]) seq[++tot]=e.ver;
	if(tot) p[u]=Light_Divide(1,tot);
	if(u!=tp) return;
	tot=0;
	for(int t=u;t;t=son[t]) seq[++tot]=t;
	auto tmp=Heavy_Divide(1,tot);
	p[u]={tmp.q[0][0],tmp.q[1][0]};
}
signed main(){
	std::scanf("%d",&n);
	for(int i=2,u,v,w;i<=n;++i) std::scanf("%d%d%d",&u,&v,&w),G[u]+={v,w},G[v]+={u,w};
	dfs(1),dfs(1,1);
	for(unsigned k=1;k!=p[1].f.size();++k) std::printf("%lld ",p[1].f[k]);
	for(n-=p[1].f.size();n;--n) std::printf("? ");
	return 0;
}

详细

Test #1:

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

input:

5
1 2 3
2 3 5
2 4 4
3 5 2

output:

5 6 ? ? 

result:

ok single line: '5 6 ? ? '

Test #2:

score: 0
Accepted
time: 0ms
memory: 22144kb

input:

10
2 8 -5
5 10 5
3 4 -5
1 6 5
3 9 5
1 7 -3
4 8 -5
10 8 -5
1 8 -3

output:

5 10 15 10 ? ? ? ? ? 

result:

ok single line: '5 10 15 10 ? ? ? ? ? '

Test #3:

score: 0
Accepted
time: 5ms
memory: 23828kb

input:

2
1 2 35

output:

35 

result:

ok single line: '35 '

Test #4:

score: 0
Accepted
time: 0ms
memory: 22780kb

input:

100
75 98 770328247
87 98 -219729992
98 35 578758971
98 93 -348642106
63 98 -638036803
83 25 -744163505
21 98 810313834
97 25 131957988
19 98 -711567435
8 25 68874404
43 98 184473508
28 94 171940607
92 28 971759198
51 98 -674532123
28 6 797727320
98 95 1154600
98 58 683765502
28 12 358426364
4 42 65...

output:

990461444 1951945471 2906346403 3825083089 4484694703 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 

result:

ok single line: '990461444 1951945471 290634640... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #5:

score: 0
Accepted
time: 5ms
memory: 23716kb

input:

203
139 160 -585848305
172 95 -541522893
170 39 5557137
106 39 -778170145
3 95 -436330773
39 6 -437501664
16 130 -452155774
65 148 68947909
160 62 959671488
109 39 -800234924
39 69 -419168940
23 16 876930246
95 84 393547919
11 39 640235516
37 95 100755747
39 36 930905421
95 103 150613974
39 60 55894...

output:

980020055 1939691543 2855429156 3756427595 4562844897 4346623326 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '980020055 1939691543 285542915... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #6:

score: 0
Accepted
time: 0ms
memory: 23364kb

input:

406
77 136 -97512557
231 136 542346963
130 177 -388708409
390 136 686852490
342 127 883069794
128 136 477257139
254 136 -475703031
136 32 -928318588
136 295 510781030
102 342 871598741
137 214 648132758
342 3 697615122
136 120 -301371460
406 43 154140155
406 55 921120861
72 371 88488927
183 136 -146...

output:

996418061 1986908701 2975920530 3898989188 4755959611 5559326552 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '996418061 1986908701 297592053... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #7:

score: 0
Accepted
time: 5ms
memory: 24988kb

input:

812
72 362 -368276642
362 196 -634964868
362 743 -833364678
244 362 78813293
111 20 -210495433
455 362 455557250
229 64 -426691307
756 362 139006554
362 143 473229314
20 534 -699191624
158 362 93363463
312 20 -859248217
157 362 180458703
362 731 299520404
20 323 -735699279
20 742 -812381447
439 20 1...

output:

999034642 1995939938 2980594575 3958550949 4917179479 5765897258 6449371168 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...

result:

ok single line: '999034642 1995939938 298059457... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #8:

score: 0
Accepted
time: 0ms
memory: 23208kb

input:

1625
1142 1405 -551024632
385 1543 919271125
398 981 264110458
385 1176 -413402000
123 385 736435016
252 385 718332198
1294 385 34067686
981 267 -384479151
1552 385 793504414
23 385 -694334331
1197 385 385229583
1016 385 -467572952
536 385 439439632
769 385 358175397
385 858 -647141736
385 178 -3958...

output:

999537220 1998889246 2996051177 3986098023 4948945555 5833220615 6655752159 6915163854 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999537220 1998889246 299605117... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #9:

score: 0
Accepted
time: 8ms
memory: 25152kb

input:

3250
2887 101 258851508
2017 1662 546412652
1662 629 -28215881
1756 1662 450358858
2981 1692 799511924
3193 1662 363320660
1692 905 -323671345
1692 2935 19706073
2913 3047 -25735169
1149 2887 -805060913
1692 461 824382188
1692 2403 929982454
2509 721 -147417737
1662 770 -721376313
1260 1662 -1568571...

output:

999996265 1997699858 2994629552 3984126644 4965926521 5932717085 6881879351 7821660229 8728166024 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...

result:

ok single line: '999996265 1997699858 299462955... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #10:

score: 0
Accepted
time: 4ms
memory: 23028kb

input:

7500
4955 6802 -495321867
6802 2205 -674830428
6287 3296 931013751
6802 7002 -972370682
5968 6802 -4844061
6802 4769 239749327
1694 6802 -468455800
6802 976 158103224
6802 5250 381161328
5281 6802 -109984276
4676 2299 563014102
2299 297 -529154962
4317 2436 861997552
3474 2299 938353692
6802 6742 11...

output:

999621933 1999210349 2998150687 3996516968 4992090923 5980299116 6965962239 7791569767 8521331693 9157667141 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999621933 1999210349 299815068... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #11:

score: 0
Accepted
time: 10ms
memory: 24088kb

input:

12500
12420 8595 -255200982
11605 5490 845231189
8595 5721 390643780
5512 5490 268180812
11132 10795 956887552
7633 8595 -622785013
7562 8595 513664257
9744 8595 -675715598
6080 8595 999680752
11864 8595 -967505600
9961 8595 613622983
1356 12167 808408582
2383 8595 -476729851
6969 11132 -942417500
2...

output:

999858209 1999538961 2999084473 3998464234 4997801190 5996643071 6995458737 7992421815 8922828463 9776715075 9864436704 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...

result:

ok single line: '999858209 1999538961 299908447... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #12:

score: 0
Accepted
time: 12ms
memory: 23136kb

input:

25000
17077 20165 -507412418
18419 20161 618820479
19707 19850 -175193487
20165 14994 943405292
20165 24206 -167254127
20706 20165 171657772
21119 20165 116133390
4987 20165 42216677
11925 11458 -917266631
3554 20165 -419663469
3565 9374 453456629
17577 20165 -721380063
23667 10268 616472024
11078 2...

output:

999925482 1999836258 2999615985 3999293406 4997527596 5994797398 6990387648 7966039593 8937696974 9843700482 10677729598 11067646897 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999925482 1999836258 299961598... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #13:

score: 0
Accepted
time: 21ms
memory: 25104kb

input:

50000
18500 2466 792046417
18500 44110 -900904087
21015 11984 -737928618
28173 41859 -519214580
30313 18500 -301917017
42387 41859 -974702020
11984 24167 146595056
18500 21584 903989466
18500 37467 556499768
41859 19205 -9960474
3769 39568 914049493
44621 18500 187544463
18500 15381 -10251112
11984 ...

output:

999937917 1999800424 2999565993 3999252320 4998654018 5997015278 6995342886 7990129710 8964115429 9930869200 10864301226 11747795394 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999937917 1999800424 299956599... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #14:

score: 0
Accepted
time: 53ms
memory: 25248kb

input:

100000
41120 8939 -908804331
41120 59419 937439044
56449 26963 281860304
56449 40366 164393802
70598 56449 17660671
32292 56449 661439314
89841 56449 850663169
56997 56449 -284803758
12053 13650 -277296534
76004 13650 367404917
13650 64459 -238013272
39862 56449 248682228
54227 19569 -913307595
4112...

output:

999969594 1999928060 2999840635 3999730309 4999609571 5999262156 6998303381 7997324865 8994564135 9989627730 10975230325 11947018149 12805065409 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999969594 1999928060 299984063... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #15:

score: 0
Accepted
time: 113ms
memory: 27804kb

input:

200000
67373 91995 -500869886
70900 10837 -54987159
126177 70900 88807696
142953 91374 61508750
141503 70900 169900986
58548 70900 -39790283
9166 148393 -599860314
69224 38404 630361305
79354 91995 763726682
56066 70900 682115260
194973 70900 -683695849
91995 5518 -141603845
182408 70900 -679035513
...

output:

999999123 1999993982 2999765931 3999482750 4999165478 5998705808 6997961293 7996356785 8994482310 9992017971 10988239271 11973337088 12834111224 13665388181 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999999123 1999993982 299976593... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #16:

score: 0
Accepted
time: 104ms
memory: 27952kb

input:

200000
189756 112654 13430889
114148 160650 551578800
32649 112654 -34474549
160650 84423 449825891
86820 112654 51028326
112654 63925 -931768736
67025 112654 -433304196
56759 112654 759335947
101542 112654 -882393322
157591 162907 205099452
112654 4322 304631080
84481 137371 576019189
112654 84131 ...

output:

999993776 1999986889 2999959226 3999926704 4999850626 5999598626 6998885935 7998000018 8994632072 9990659751 10986088637 11971120882 12918372872 13799062553 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999993776 1999986889 299995922... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #17:

score: 0
Accepted
time: 109ms
memory: 28040kb

input:

200000
194800 126799 652392877
118542 15648 772985966
2384 192813 423677466
153032 118542 -936812159
118542 66351 233167978
2947 118542 -3489841
119976 61565 201430819
2384 183169 405267510
2384 7689 559930836
129177 2384 971258417
61565 42998 -77981354
77645 199693 296926917
77645 144046 -174125055...

output:

999990735 1999968004 2999892750 3999805282 4999700699 5999543390 6999373840 7999201268 8998994995 9998721590 10998385197 11998017215 12997521832 13996497922 14994553103 15991145807 16986134816 17977297611 18966733091 19952183794 20933598167 21885590012 22384966407 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999990735 1999968004 299989275... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #18:

score: 0
Accepted
time: 98ms
memory: 27408kb

input:

200000
60041 170200 987254314
92021 166355 485601524
40677 197699 704297812
197699 192825 742511399
197699 97740 173194821
197699 12951 168789082
111438 197699 323448281
61019 60041 -42458590
147478 138403 340309850
197699 12212 683586111
95531 197699 -566048102
183050 92021 -395511865
14148 197699 ...

output:

999985972 1999970432 2999933318 3999893410 4999850620 5999780890 6999594495 7999333547 8999023075 9998638365 10997980154 11997144762 12995932422 13994550499 14991761388 15985565406 16973260397 17950241218 18880036931 19779712151 20595262331 21071775853 21467465622 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

result:

ok single line: '999985972 1999970432 299993331... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #19:

score: 0
Accepted
time: 112ms
memory: 27424kb

input:

200000
19337 99274 21161960
83182 3228 752596214
35885 101792 842700467
63267 140995 311553404
77632 48159 301866496
117878 122644 474823297
114799 48159 -731449436
172086 117878 -156508734
117878 60088 72729516
19337 63450 -484286312
191350 63267 -138496028
71028 53815 -20919695
19337 108298 -60484...

output:

999979936 1999959867 2999939467 3999911319 4999852355 5999780968 6999683908 7999575497 8999417561 9999206697 10998877612 11998362182 12997514663 13996085094 14994446395 15992726156 16990293225 17987547960 18984406018 19977031341 20969045834 21959110181 22935708909 23909537938 24877433488 25838110855...

result:

ok single line: '999979936 1999959867 299993946... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #20:

score: 0
Accepted
time: 107ms
memory: 27404kb

input:

200000
155704 57519 -182661550
66259 61288 -473817517
139972 66259 1775759
32838 147826 571025716
194796 66259 279929288
57519 106539 -550321979
74265 66259 899176123
46030 66259 591562374
91299 57519 -798765652
169916 124893 -533272184
159491 124893 256735685
57519 69366 771042667
171875 147826 -79...

output:

999977654 1999940765 2999898128 3999840227 4999773505 5999700183 6999623737 7999464491 8999285184 9998979617 10998452550 11997821827 12996927030 13995893102 14994783173 15993400674 16991556699 17989389762 18987100306 19983042712 20972703332 21962114266 22950120078 23938027315 24920738011 25903337971...

result:

ok single line: '999977654 1999940765 299989812... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #21:

score: 0
Accepted
time: 109ms
memory: 27608kb

input:

200000
35696 98797 484336770
141756 25396 -943057028
16026 81023 380350226
16889 121640 -346617727
141756 157830 235275721
176446 36397 485986735
191893 48084 463674400
165525 121640 839739745
26747 191893 605352498
184606 141756 -27776080
152271 37052 310891025
166066 191893 657764647
141756 36365 ...

output:

999984415 1999967672 2999941138 3999911221 4999859661 5999795417 6999716373 7999631433 8999506302 9999358614 10999128418 11998828423 12998397083 13997756369 14997010443 15996254644 16995234334 17993873508 18992438216 19990935894 20988955880 21986002441 22982380829 23977714533 24971271876 25962659481...

result:

ok single line: '999984415 1999967672 299994113... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #22:

score: 0
Accepted
time: 117ms
memory: 27888kb

input:

200000
26015 4329 -708576109
192563 116104 -166593315
179803 23299 849180025
194423 23299 -11726072
192563 43985 -457910096
10256 87997 126799668
4329 174277 643815213
43532 45060 -902477730
65068 96990 464198681
5201 171752 -74354084
184295 36807 -964401553
65068 92141 922727530
125074 36546 290119...

output:

999988301 1999967771 2999942899 3999916494 4999889463 5999841942 6999765495 7999676566 8999553912 9999427641 10999280350 11999016200 12998670581 13998170958 14997464892 15996575863 16995048328 17993201896 18991339412 19989323139 20986738595 21983743714 22980738077 23977214483 24971804730 25965857284...

result:

ok single line: '999988301 1999967771 299994289... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #23:

score: 0
Accepted
time: 115ms
memory: 27772kb

input:

200000
125404 174796 944048923
192769 112134 -929636531
175796 74880 -325743791
174796 194528 194513081
34556 163257 -601094028
83938 121529 -138933326
195976 154687 -58094569
131336 83938 424337833
2082 83938 -522506486
186022 115020 -684778390
97243 83938 911014076
161435 83938 722334407
6060 1820...

output:

999978301 1999936914 2999886410 3999835039 4999763073 5999655533 6999544041 7999431094 8999308993 9999134847 10998927150 11998694182 12998357668 13997856356 14997343736 15996822336 16996159811 17995326898 18993875962 19992143185 20989857186 21987020326 22984027112 23980519825 24976886301 25972980109...

result:

ok single line: '999978301 1999936914 299988641... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #24:

score: 0
Accepted
time: 104ms
memory: 27608kb

input:

200000
76405 125001 -304846664
170279 46973 295505338
26674 134878 -815732288
58484 173573 744497446
76403 119102 -495765873
159371 134878 166770985
51978 187106 540805599
51978 18999 -120847608
39030 173573 -899102602
173573 28591 -368046824
51978 73185 -132705011
51978 121276 557546808
121890 4697...

output:

999988985 1999973524 2999955163 3999918234 4999877700 5999834235 6999765381 7999656665 8999545861 9999417589 10999273468 11999096944 12998529015 13997935012 14997313759 15996651965 16995958074 17995255453 18994368412 19993383417 20992268900 21990878987 22989445672 23987943842 24985563692 25982560154...

result:

ok single line: '999988985 1999973524 299995516... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #25:

score: 0
Accepted
time: 118ms
memory: 28128kb

input:

200000
186231 139021 -902189812
162370 172758 285145484
34567 57879 781633790
90199 195703 -5706328
74109 48797 -729569396
42828 165009 430950687
11303 57879 -430820728
162370 165877 945741453
90199 124361 973189425
120077 198622 161706318
131572 18520 -738307833
139021 106387 -979669543
149986 1690...

output:

999994624 1999987632 2999979904 3999922442 4999855996 5999768959 6999681389 7999587265 8999446214 9999273883 10999072258 11998798898 12998523651 13998178792 14997832876 15997402543 16996959792 17996486157 18995988260 19995326947 20994646386 21993732471 22992757105 23991624210 24990413732 25988827988...

result:

ok single line: '999994624 1999987632 299997990... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #26:

score: 0
Accepted
time: 115ms
memory: 27616kb

input:

200000
80814 164073 -556034029
166374 64891 -161316740
136967 174971 643154762
184380 102688 994062239
167505 64404 -765963543
184380 52209 -794047719
188170 85085 327900047
141570 114474 -740850562
73962 198833 237503131
14063 30445 536210010
188170 199744 -832294279
80814 109705 932212290
181161 1...

output:

999991752 1999977757 2999956968 3999927054 4999888470 5999795326 6999698906 7999600218 8999472768 9999322523 10999149856 11998900580 12998635380 13998336203 14998006175 15997671734 16997289406 17996902465 18996492857 19996041836 20995587146 21995128301 22993931770 23992668844 24991183368 25989668644...

result:

ok single line: '999991752 1999977757 299995696... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '

Test #27:

score: -100
Wrong Answer
time: 227ms
memory: 54716kb

input:

200000
197046 67880 827032577
12531 50788 -262644034
27588 19015 340163763
127935 109408 -259169107
121122 70801 185118022
183232 65075 -461756034
139342 44501 729189417
143884 40265 871687635
24782 100333 259093247
63674 27794 -898163805
48471 89004 -436766263
111125 90426 525775439
169583 68605 -2...

output:

999977978 1999955255 2999924225 3999886064 4999824892 5999750170 6999671225 7999585490 8999489852 9999388848 10999280640 11999165329 12999042301 13998918536 14998775948 15998630977 16998477719 17998322496 18998146294 19997962536 20997767812 21997524219 22997278504 23997027025 24996771299 25996512751...

result:

wrong answer 1st lines differ - expected: '999977978 1999955255 299992422...? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?', found: '999977978 1999955255 299992422... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '