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 |
---|---|---|---|---|---|---|
1774 | Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) | FINISHED | False | 9000 | 65978663 | Dec. 17, 2022, 2:35 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 137 ) | H | Maximum Permutation | PROGRAMMING | constructive algorithms |
B'Ecrade bought a deck of cards numbered from 1 to n . Let the value of a permutation a of length n be min limits_{i = 1}^{n - k + 1} sum limits_{j = i}^{i + k - 1}a_j . Ecrade wants to find the most valuable one among all permutations of the cards. However, it seems a little difficult, so please help him! The first line contains a single integer t ( 1 <= q t <= q 2 cdot 10^4 ) -- the number of test cases. The description of test cases follows. The only line of each test case contains two integers n,k ( 4 <= q k < n <= q 10^5 ). It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^6 . For each test case, output the largest possible value in the first line. Then in the second line, print n integers a_1,a_2, ... ,a_n ( 1 <= a_i <= n , all a_i are distinct) -- the elements of the permutation that has the largest value. If there are multiple such permutations, output any of them. In the first test case, [1,4,5,3,2] has a value of 13 . It can be shown that no permutations of length 5 have a value greater than 13 when k = 4 . In the second test case, [4,2,5,7,8,3,1,6] has a value of 18 . It can be shown that no permutations of length 8 have a value greater than 18 when k = 4 . '... |
Polynomial Round 2022 (Div. 1 + Div. 2) Editorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
185749585 | Ahmad_Hajjouz | H | Dec. 18, 2022, 5:26 a.m. | OK | GNU C++17 (64) | TESTS | 34 | 545 | 1638400 |
Back to search problems