题目名称	2642. [SHOI 2015] 自动刷题机
输入输出	`autoac.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	20
题目来源	Robin_Lu 于2017-03-30加入
开放分组	全部用户
提交状态
分类标签	二分法
	分享题解

通过：19，提交：71，通过率：26.76%
HeHe	100	0.220 s	0.95 MiB	C++
liumy	100	0.317 s	0.66 MiB	C++
TARDIS	100	0.339 s	0.43 MiB	C++
沉迷学习的假的Keller	100	0.343 s	0.43 MiB	C++
kZime	100	0.404 s	1.08 MiB	C++
Emine	100	0.450 s	0.67 MiB	C++
Imone NOI2018Au	100	0.461 s	0.67 MiB	C++
哒哒哒哒哒！	100	0.518 s	8.02 MiB	C++
Robin_Lu	100	0.522 s	1.05 MiB	C++
niconicoqaq	100	0.568 s	1.07 MiB	C++

本题关联比赛
假期找点事儿做题吧

关于自动刷题机的近10条评论(全部评论)
无数细节对着数据调代码 CSU_Turkey 2017-08-01 19:16 8楼
样例: `1 1 2 2 2 2 3 3 3 l r l r` 没加读入优化就上榜了？？ kZime 2017-06-23 09:39 7楼
二分答案 nlogn的。话说卡了bug的没有我这个没卡bug的跑得快23333 HeHe 2017-06-23 09:16 6楼
我竟然对于无解的情况，输出了两个-1 QAQ人傻 niconicoqaq 2017-05-11 21:12 5楼
大概pj题目吧我果然是跑的坠慢的 __stdcall 2017-04-07 10:32 4楼
康哥厉害，真狠！！！ LOSER 2017-04-04 12:11 3楼
long long 各种挂...强行拉低正确率QAQ 沉迷学习的假的Keller 2017-03-31 09:16 2楼
呵呵 zyf 2017-03-30 19:54 1楼

2642. [SHOI 2015] 自动刷题机

★★★ 输入文件：autoac.in 输出文件：autoac.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明：自动刷题机--一种可以自动AC题目的神秘装置。自动

刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序，每秒，自动刷题机的代码生成模

块会有两种可能的结果：

A.写了x行代码。

B.心情不好，删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删除。）

对于每个OJ所有题目，存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累了大于等于n行的代码，它就会

自动提交并AC此题，然后新建一个文件开始写下一题。SHTSC在某个OJ上跑了一天的自动刷题机，得到了很多条关

于写代码的日志信息。他突然发现自己没有记录这个OJ的n究竟是多少。所幸他通过自己在OJ上的Rank知道了机一

共切了k道题。希望你计算n可能的最小值和最大值。

【输入格式】

第一行两个整数l，k，表示刷题机的日志一共有l行，一共了切了k题。

第二行l个整数，x1…xl。xi>=0表示写了xi行代码。xi<0表示删除了这道题的-xi行代码。

1<=l,k<=100000，|xi|<=10^9

【输出格式】

输出两个数a，b。分别代表n可能的最小值和最大值。如果不存在这样的n则输出-1。

【样例输入】

【样例输出】

3 7
  //样例1：如果n=2那么刷题机就会切掉3题。但如果n>7刷题机最多只能切1题。考虑n=4发生了什么。
  第一秒：刷题机写了2行。
  第二秒：刷题机又写了5行，共有7行，提交，自信AC。
  第三秒：刷题机删掉了3行，共有0行。
  第四秒：刷题机写了9行，共有9行，提交，自信AC。
  一共AC了两题。

2642. [SHOI 2015] 自动刷题机

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

【来源】

【题目来源】