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 |
---|---|---|---|---|---|---|
1809 | Educational Codeforces Round 145 (Rated for Div. 2) | FINISHED | False | 7200 | 57684263 | March 23, 2023, 2:35 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 460 ) | G | Prediction | PROGRAMMING | combinatorics data structures dp |
B'Consider a tournament with n participants. The rating of the i -th participant is a_i . The tournament will be organized as follows. First of all, organizers will assign each participant an index from 1 to n . All indices will be unique. Let p_i be the participant who gets the index i . Then, n-1 games will be held. In the first game, participants p_1 and p_2 will play. In the second game, the winner of the first game will play against p_3 . In the third game, the winner of the second game will play against p_4 , and so on -- in the last game, the winner of the (n-2) -th game will play against p_n . Monocarp wants to predict the results of all n-1 games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings x and y play, and |x - y| > k , the participant with the higher rating wins. But if |x - y| <= k , any of the two participants may win. Among all n! ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all n-1 games. Since the answer can be large, print it modulo 998244353 . The first line contains two integers n and k ( 2 <= n <= 10^6 ; 0 <= k <= 10^9 ). The second line contains n integers a_1, a_2, ... , a_n ( 0 <= a_1 <= a_2 <= ... <= a_n <= 10^9 ). Print one integer -- the number of ways to assign the indices to the participants so that Monocarp can predict the results of all n-1 games. In the first example, a match with any pair of players can be predicted by Monocarp, so all 24 ways to assign indices should be counted. In the second example, suitable ways are [1, 3, 2] , [2, 3, 1] , [3, 1, 2 ] and [3, 2, 1] . '... |
114300 |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
198880173 | LXH-cat | G | March 24, 2023, 1:12 a.m. | OK | GNU C++14 | TESTS | 53 | 358 | 24371200 | ||
198829692 | stkwill | G | March 23, 2023, 4:38 p.m. | OK | GNU C++14 | TESTS | 53 | 374 | 24064000 | ||
198893667 | donghanwen | G | March 24, 2023, 5:16 a.m. | OK | GNU C++14 | TESTS | 53 | 1747 | 40038400 | ||
198885423 | zft_4995 | G | March 24, 2023, 3:06 a.m. | OK | GNU C++17 | TESTS | 53 | 327 | 12083200 | ||
198859922 | 2023_365_streak | G | March 23, 2023, 8:27 p.m. | OK | GNU C++17 | TESTS | 53 | 343 | 12083200 | ||
198840833 | gautamankoji | G | March 23, 2023, 5:36 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 202 | 12083200 | ||
198828608 | tute7627 | G | March 23, 2023, 4:34 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 233 | 28057600 | ||
198832652 | potato167 | G | March 23, 2023, 4:50 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 234 | 40140800 | ||
198837763 | pawan1712 | G | March 23, 2023, 5:17 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 1170 | 16076800 | ||
198831844 | Rubikun | G | March 23, 2023, 4:46 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 1216 | 33075200 | ||
198829525 | Rubikun | G | March 23, 2023, 4:37 p.m. | OK | GNU C++17 (64) | TESTS | 53 | 2386 | 37273600 |
Back to search problems