Codeforces Round 683 (Div. 1, by Meet IT)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1446 Codeforces Round 683 (Div. 1, by Meet IT) FINISHED False 9000 126372299 Nov. 15, 2020, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 15662 ) A Knapsack PROGRAMMING constructive algorithms greedy sortings

B"You have a knapsack with the capacity of W . There are also n items, the i -th one has weight w_i . You want to put some of these items into the knapsack in such a way that their total weight C is at least half of its size, but (obviously) does not exceed it. Formally, C should satisfy: lceil frac{W}{2} rceil <= C <= W . Output the list of items you will put into the knapsack or determine that fulfilling the conditions is impossible. If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights of items in the knapsack. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 10^4 ). Description of the test cases follows. The first line of each test case contains integers n and W ( 1 <= n <= 200 ,000 , 1 <= W <= 10^{18} ). The second line of each test case contains n integers w_1, w_2, ... , w_n ( 1 <= w_i <= 10^9 ) -- weights of the items. The sum of n over all test cases does not exceed 200 ,000 . For each test case, if there is no solution, print a single integer -1 . If there exists a solution consisting of m items, print m in the first line of the output and m integers j_1 , j_2 , ..., j_m ( 1 <= j_i <= n , all j_i are distinct) in the second line of the output -- indices of the items you would like to pack into the knapsack. If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights items in the knapsack. In the first test case, you can take the item of weight 3 and fill the knapsack just right. In the second test case, all the items are larger than the knapsack's capacity. Therefore, the answer is -1 . In the third test case, you fill the knapsack exactly "...

Tutorials

E

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
98447746 Gassa A Nov. 15, 2020, 2:43 p.m. OK D TESTS 20 124 13516800
98516705 prakash.4 A Nov. 16, 2020, 3:51 a.m. OK GNU C11 TESTS 20 733 1638400
98445450 LJC00118 A Nov. 15, 2020, 2:39 p.m. OK GNU C++11 TESTS 20 31 2355200
98518104 huanggs A Nov. 16, 2020, 4:33 a.m. OK GNU C++11 TESTS 20 46 136089600
98451362 fr200110217102 A Nov. 15, 2020, 2:48 p.m. OK GNU C++11 TESTS 20 61 2457600
98457222 RandomID7896 A Nov. 15, 2020, 3 p.m. OK GNU C++11 TESTS 20 62 19148800
98451329 MrGary A Nov. 15, 2020, 2:48 p.m. OK GNU C++11 TESTS 20 77 1536000
98453757 srijon51 A Nov. 15, 2020, 2:53 p.m. OK GNU C++11 TESTS 20 77 4710400
98448261 wh0816 A Nov. 15, 2020, 2:43 p.m. OK GNU C++11 TESTS 20 77 6348800
98446317 mlby A Nov. 15, 2020, 2:40 p.m. OK GNU C++11 TESTS 20 77 7987200
98450239 Kaycee A Nov. 15, 2020, 2:47 p.m. OK GNU C++11 TESTS 20 77 7987200
98446998 zhylj A Nov. 15, 2020, 2:41 p.m. OK GNU C++11 TESTS 20 77 7987200
98479566 yinghua1314 A Nov. 15, 2020, 4:04 p.m. OK GNU C++14 TESTS 20 46 4300800
98450270 yhx-12243 A Nov. 15, 2020, 2:47 p.m. OK GNU C++14 TESTS 20 77 1638400
98513859 mrbb_twinhter A Nov. 16, 2020, 2:19 a.m. OK GNU C++14 TESTS 20 77 1638400
98462430 cfabcdhhhh A Nov. 15, 2020, 3:12 p.m. OK GNU C++14 TESTS 20 77 2457600
98449849 farmerboy A Nov. 15, 2020, 2:46 p.m. OK GNU C++14 TESTS 20 77 2457600
98453687 chpipis A Nov. 15, 2020, 2:53 p.m. OK GNU C++14 TESTS 20 77 2457600
98448030 adurysk A Nov. 15, 2020, 2:43 p.m. OK GNU C++14 TESTS 20 77 3174400
98446653 vsriram1012 A Nov. 15, 2020, 2:41 p.m. OK GNU C++14 TESTS 20 77 4812800
98499883 caoash A Nov. 15, 2020, 6:41 p.m. OK GNU C++14 TESTS 20 77 7987200
98447521 ugly2333 A Nov. 15, 2020, 2:42 p.m. OK GNU C++14 TESTS 20 78 921600
98447095 wleung_bvg A Nov. 15, 2020, 2:42 p.m. OK GNU C++17 TESTS 20 46 3379200
98448823 Unsterblicher_Geist A Nov. 15, 2020, 2:44 p.m. OK GNU C++17 TESTS 20 46 5222400
98445782 LayCurse A Nov. 15, 2020, 2:39 p.m. OK GNU C++17 TESTS 20 46 101478400
98448222 _Backl1ght A Nov. 15, 2020, 2:43 p.m. OK GNU C++17 TESTS 20 61 4300800
98456529 Vedensky A Nov. 15, 2020, 2:59 p.m. OK GNU C++17 TESTS 20 77 819200
98448175 Timur_Sitdikov A Nov. 15, 2020, 2:43 p.m. OK GNU C++17 TESTS 20 77 1638400
98453345 codelegend A Nov. 15, 2020, 2:52 p.m. OK GNU C++17 TESTS 20 77 1638400
98446197 csani A Nov. 15, 2020, 2:40 p.m. OK GNU C++17 TESTS 20 77 1638400
98509928 cuiaoxiang A Nov. 15, 2020, 11:26 p.m. OK GNU C++17 TESTS 20 77 2457600
98485682 VaVshchuck A Nov. 15, 2020, 4:30 p.m. OK GNU C++17 TESTS 20 77 2457600
98497003 LayCurse A Nov. 15, 2020, 5:59 p.m. OK GNU C++17 (64) TESTS 20 31 101478400
98447670 compute A Nov. 15, 2020, 2:42 p.m. OK GNU C++17 (64) TESTS 20 46 3993600
98450564 yosupo A Nov. 15, 2020, 2:47 p.m. OK GNU C++17 (64) TESTS 20 46 5427200
98445457 -____- A Nov. 15, 2020, 2:39 p.m. OK GNU C++17 (64) TESTS 20 46 5836800
98449886 HNO2 A Nov. 15, 2020, 2:46 p.m. OK GNU C++17 (64) TESTS 20 46 12288000
98447072 jiangly A Nov. 15, 2020, 2:41 p.m. OK GNU C++17 (64) TESTS 20 61 2150400
98449288 KhaledRezk A Nov. 15, 2020, 2:45 p.m. OK GNU C++17 (64) TESTS 20 61 2969600
98446258 RobeZH A Nov. 15, 2020, 2:40 p.m. OK GNU C++17 (64) TESTS 20 61 2969600
98445752 tfg A Nov. 15, 2020, 2:39 p.m. OK GNU C++17 (64) TESTS 20 61 3788800
98506530 Monazo1997 A Nov. 15, 2020, 9:14 p.m. OK GNU C++17 (64) TESTS 20 61 3788800
98449429 synapse A Nov. 15, 2020, 2:45 p.m. OK Go TESTS 20 156 5529600
98447086 uwi A Nov. 15, 2020, 2:42 p.m. OK Java 11 TESTS 20 218 819200
98452013 nick_301 A Nov. 15, 2020, 2:50 p.m. OK Java 11 TESTS 20 326 4812800
98453285 skittles1412 A Nov. 15, 2020, 2:52 p.m. OK Java 11 TESTS 20 342 7168000
98455016 rohan03 A Nov. 15, 2020, 2:56 p.m. OK Java 11 TESTS 20 343 6553600
98450302 Apfeloxid A Nov. 15, 2020, 2:47 p.m. OK Java 11 TESTS 20 343 13926400
98445435 qwerty787788 A Nov. 15, 2020, 2:39 p.m. OK Java 11 TESTS 20 358 7577600
98501533 rreeennnnn A Nov. 15, 2020, 7:10 p.m. OK Java 11 TESTS 20 389 15257600
98457414 mphillotry A Nov. 15, 2020, 3:01 p.m. OK Java 11 TESTS 20 420 10035200
98520252 ms2020 A Nov. 16, 2020, 5:22 a.m. OK Java 11 TESTS 20 842 4915200
98500899 tankman890 A Nov. 15, 2020, 6:59 p.m. OK Java 11 TESTS 20 1014 0
98451414 martins A Nov. 15, 2020, 2:49 p.m. OK Java 8 TESTS 20 155 6758400
98447062 fetetriste A Nov. 15, 2020, 2:41 p.m. OK Java 8 TESTS 20 171 3584000
98503643 irazvi1890 A Nov. 15, 2020, 7:53 p.m. OK Java 8 TESTS 20 186 3686400
98446794 SecondThread A Nov. 15, 2020, 2:41 p.m. OK Java 8 TESTS 20 202 3686400
98445824 cwise A Nov. 15, 2020, 2:39 p.m. OK Java 8 TESTS 20 218 0
98452522 adp527 A Nov. 15, 2020, 2:51 p.m. OK Java 8 TESTS 20 249 9625600
98447583 ijxjdjd A Nov. 15, 2020, 2:42 p.m. OK Java 8 TESTS 20 264 4608000
98449554 jxin31415 A Nov. 15, 2020, 2:45 p.m. OK Java 8 TESTS 20 264 5836800
98453894 golions A Nov. 15, 2020, 2:53 p.m. OK Java 8 TESTS 20 264 7987200
98496136 2020akadaver A Nov. 15, 2020, 5:50 p.m. OK Java 8 TESTS 20 264 12595200
98497523 AryssonFigueiredo A Nov. 15, 2020, 6:06 p.m. OK Kotlin TESTS 20 202 0
98450357 simenl A Nov. 15, 2020, 2:47 p.m. OK Kotlin TESTS 20 342 18944000
98452875 amelentev A Nov. 15, 2020, 2:51 p.m. OK Kotlin TESTS 20 343 16281600
98495387 Tlatoani A Nov. 15, 2020, 5:42 p.m. OK Kotlin TESTS 20 358 19558400
98499186 horvat.kamca A Nov. 15, 2020, 6:30 p.m. OK Kotlin TESTS 20 389 16896000
98450720 MixaPlt A Nov. 15, 2020, 2:47 p.m. OK Kotlin TESTS 20 936 36147200
98449958 P___ A Nov. 15, 2020, 2:46 p.m. OK MS C++ 2017 TESTS 20 124 3276800
98454463 tarattata1 A Nov. 15, 2020, 2:55 p.m. OK MS C++ 2017 TESTS 20 140 3174400
98448346 Khas_Profit_LLC A Nov. 15, 2020, 2:44 p.m. OK MS C++ 2017 TESTS 20 202 5017600
98448796 Catmoonlight A Nov. 15, 2020, 2:44 p.m. OK MS C++ 2017 TESTS 20 264 3379200
98447772 gnomina007 A Nov. 15, 2020, 2:43 p.m. OK MS C++ 2017 TESTS 20 280 5017600
98448804 AnnSuperstar A Nov. 15, 2020, 2:44 p.m. OK MS C++ 2017 TESTS 20 280 6348800
98448266 mban259 A Nov. 15, 2020, 2:43 p.m. OK .NET Core C# TESTS 20 124 29491200
98447648 azukun A Nov. 15, 2020, 2:42 p.m. OK .NET Core C# TESTS 20 171 30412800
98445425 Yupiteru A Nov. 15, 2020, 2:39 p.m. OK .NET Core C# TESTS 20 264 23859200
98450416 keymoon A Nov. 15, 2020, 2:47 p.m. OK .NET Core C# TESTS 20 311 30515200
98454749 astrom.lars A Nov. 15, 2020, 2:55 p.m. OK PyPy 2 TESTS 20 654 20787200
98447994 yuusanlondon A Nov. 15, 2020, 2:43 p.m. OK PyPy 3 TESTS 20 295 20275200
98451182 asdsasd A Nov. 15, 2020, 2:48 p.m. OK PyPy 3 TESTS 20 342 18739200
98452017 nagiss A Nov. 15, 2020, 2:50 p.m. OK PyPy 3 TESTS 20 342 26521600
98504859 TLEincarnate A Nov. 15, 2020, 8:24 p.m. OK PyPy 3 TESTS 20 373 17817600
98448254 chinerist A Nov. 15, 2020, 2:43 p.m. OK PyPy 3 TESTS 20 373 18739200
98447932 qwertz73355a A Nov. 15, 2020, 2:43 p.m. OK PyPy 3 TESTS 20 373 18739200
98447637 SPD_9X2 A Nov. 15, 2020, 2:42 p.m. OK PyPy 3 TESTS 20 374 18739200
98505130 TLEincarnate A Nov. 15, 2020, 8:31 p.m. OK PyPy 3 TESTS 20 389 17920000
98446916 titia A Nov. 15, 2020, 2:41 p.m. OK PyPy 3 TESTS 20 405 18739200
98508296 otzhora123 A Nov. 15, 2020, 10:14 p.m. OK PyPy 3 TESTS 20 545 18739200
98452433 nwi A Nov. 15, 2020, 2:51 p.m. OK Python 2 TESTS 20 529 22425600
98508093 Nah1d A Nov. 15, 2020, 10:06 p.m. OK Python 3 TESTS 20 514 14131200
98456326 r57shell A Nov. 15, 2020, 2:58 p.m. OK Python 3 TESTS 20 545 23654400
98451778 mkawa2 A Nov. 15, 2020, 2:49 p.m. OK Python 3 TESTS 20 701 22835200
98448369 Stephan A Nov. 15, 2020, 2:44 p.m. OK Python 3 TESTS 20 888 24166400
98447154 sansen A Nov. 15, 2020, 2:42 p.m. OK Rust TESTS 20 62 8396800
98454673 Russell_Emerine A Nov. 15, 2020, 2:55 p.m. OK Rust TESTS 20 187 11264000
98451191 GeoffreyY A Nov. 15, 2020, 2:48 p.m. OK Rust TESTS 20 202 9216000

remove filters

Back to search problems