Head-on solution have complexity O(2^40)=O(10^12). It's very slow. How do it faster? I used 40=30+20 First 20- memorization second 20 as 2^20=10000000- that normaly Could you explain your solution more in detail? "First 20- memorization" What it mean in Russian? I understood that what we do with second 20. But can not understood that what we do with first 20. =) I meant that first 20 also as 2^20 or with brute force aproach, but result of first 20 we place in arr[1..1000000](memorization) sort arr than in second 20 use log-bin search in arr. Thank you very much. You is good man! I got AC. =) It's a bit more complicated than that because you should care about rod not getting off the rails during the process as well, so you can't just pick arbitrary memorized sequence which gives suitable end-result, it also must stay within limits while it performs memorized shiftings. Looks like segment tree algo, not just plain binary search (or tests are very weak). P.S: Got AC with 0.5 sec and 44Mb, probably could've done better. For every 2^20 endings I track range of start values where it is suitable (i.e. fits for its entire internal history), then for every 2^20 beginnings (sorted) I track min/max of currently active segments via two heaps. Edited by author 16.08.2022 11:51 P.P.S: Ah, I'm dumb! Memorizing first 20 leads to much easier algo when last 20 are brute-forced (not vice versa). 0.265 sec, 7 Mb. Yet, coding that monster from previous "P.S" was fun :) n, s, k = map(int, input().split()) a = 1 << s for u in map(int, input().split()): a = a >> u | (a & (1 << n+1-u) - 1) << u print((a & -a).bit_length() - 1, a.bit_length() - 1) Edited by author 29.09.2021 19:50 I got WA1 and I don't understand why. Give me some tests please. Test #1 describe into problem statement. 10 3 3 4 5 1 What it means, we have range [0, 10] and start position in 3. And have 3 shifts. First shift we can go from 3 to [-1, 7] as -1 not in range we have only [7] positions. Second shift we can go to positions [2, 12] as 12 not in range we have only [2] position. Third shift we can go to positions [1, 3] as all of them in range we have 2 possible final states 1 and 3, minimal of them 1 and maximal 3. Answer will be 1 3. Another test: 100 50 4 1 2 4 8 Possible positions on steps: 0) [50] 1) [49, 51] 2) [47, 49, 51, 53] 3) [43, 45, 47, 49, 51, 53, 55, 57] 4) [35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65] Answer will be 35 65 My program get WA3, but work right on my tests. I can't find a mistake. Please, give me some tests. Also, why 0<=s<=n and n>0 ? Is it incorrect statement? For WA3, check how you initialize the global min and max depth. n > 0 is fine. n cannot be zero, but s can be. My program works in my cases. But i have WA#12. Why? |
|