QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246541 | #7419. Jiry Matchings | qL | WA | 227ms | 54716kb | C++14 | 8.3kb | 2023-11-10 21:55:52 | 2023-11-10 21:55:53 |
Judging History
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... ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? '