Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]

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
1423 Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] FINISHED False 10800 135449711 Oct. 5, 2020, 1:05 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 108 ) I Lookup Tables PROGRAMMING bitmasks

B'John has Q closed intervals of consecutive 2K -bit numbers [l_i, r_i] and one 16-bit value v_i for each interval. ( 0 <= q i < Q ) John wants to implement a function F that maps 2K -bit numbers to 16-bit numbers in such a way that inputs from each interval are mapped to that interval 's value. In other words: F(x) = v_i, ; textrm{for every } 0 <= q i < Q ; textrm{, and every } x in [l_i, r_i] The output of F for other inputs is unimportant. John wants to make his implementation of F fast so he has decided to use lookup tables. A single 2K -bit lookup table would be too large to fit in memory, so instead John plans to use two K-bit lookup tables, LSBTable and MSBTable. His implementation will look like this: F(x) = textrm{LSBTable}[ textrm{lowKBits}(x)] ; & ; textrm{MSBTable}[ textrm{highKBits}(x)] In other words it returns the "bitwise and" of results of looking up the K least significant bits in LSBTable and the K most significant bits in MSBTable. John needs your help. Given K , Q and Q intervals [l_i, r_i] and values v_i , find any two lookup tables which can implement F or report that such tables don 't exist. The first line contains two integers K and Q ( 1 <= K <= 16 , 1 <= Q <= 2 cdot 10^5 ). Each of the next Q lines contains three integers l_i , r_i and v_i . ( 0 <= q l_i <= q r_i < 2^{2K} , 0 <= q v_i < 2^{16} ). On the first line output "possible" (without quotes) if two tables satisfying the conditions exist, or "impossible" (without quotes) if they don 't exist. If a solution exists, in the next 2 cdot 2^K lines your program should output all values of the two lookup tables (LSBTable and MSBTable) it found. When there are multiple pairs of tables satisfying the conditions, your program may output any such pair. On lines 1 + i output textrm{LSBTable}[i] . ( 0 <= q i < 2^K ,'...

Tutorials

FinalsEditorial2020.pdf

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
94812535 TiwAirOAO I Oct. 6, 2020, 1:15 a.m. OK GNU C++11 TESTS 36 139 13209600
94784579 Cyanic ix35 s_r_f I Oct. 5, 2020, 3:14 p.m. OK GNU C++11 TESTS 36 187 14131200
94812338 Drice I Oct. 6, 2020, 1:08 a.m. OK GNU C++14 TESTS 36 295 70553600
94775230 nnandi Zoli9 bazsi700 I Oct. 5, 2020, 1:55 p.m. OK GNU C++14 TESTS 36 374 39116800
94792513 milisav I Oct. 5, 2020, 4:32 p.m. OK GNU C++17 TESTS 36 233 27852800
94792037 milisav I Oct. 5, 2020, 4:25 p.m. OK GNU C++17 TESTS 36 249 46182400
94788907 Batrr Sealionheart parasat I Oct. 5, 2020, 3:52 p.m. OK GNU C++17 TESTS 36 249 49561600
94792958 Sorting I Oct. 5, 2020, 4:38 p.m. OK GNU C++17 TESTS 36 342 80896000
94789073 Amoo_Safar Atreus Shayan.P I Oct. 5, 2020, 3:54 p.m. OK GNU C++17 TESTS 36 374 7987200
94793265 wiwitrifai I Oct. 5, 2020, 4:42 p.m. OK GNU C++17 TESTS 36 452 11571200
94786050 tourist I Oct. 5, 2020, 3:26 p.m. OK GNU C++17 TESTS 36 483 6144000
94793064 wiwitrifai I Oct. 5, 2020, 4:39 p.m. OK GNU C++17 TESTS 36 514 12697600
94793115 wiwitrifai I Oct. 5, 2020, 4:40 p.m. OK GNU C++17 TESTS 36 545 12697600
94791688 Umi I Oct. 5, 2020, 4:20 p.m. OK GNU C++17 TESTS 36 592 30617600
94796326 greencis I Oct. 5, 2020, 5:31 p.m. OK GNU C++17 (64) TESTS 36 156 7168000
94782525 Merkurev Um_nik I Oct. 5, 2020, 2:55 p.m. OK GNU C++17 (64) TESTS 36 436 14028800
94783978 hos.lyric maroonrk yosupo I Oct. 5, 2020, 3:08 p.m. OK GNU C++17 (64) TESTS 36 483 13004800
94788701 SunshinePie CN_zwang2002 YangDavid I Oct. 5, 2020, 3:50 p.m. OK GNU C++17 (64) TESTS 36 498 22835200

remove filters

Back to search problems