IOIGuaranteedPlace
SRM 808 · 2021-06-23 · by misof
SRM 808 · 2021-06-23 · by misof · Simple Math, Sorting
Problem Statement
Problem Statement
The International Olympiad in Informatics (IOI) is currently in progress. To honor this competition, our problems for this round have IOI-flavored stories.
N contestants, numbered 0 to N-1, are taking part in the IOI.
Day 1 is already over. For each i, contestant i scored day1scores[i] points. Day 2 is currently in progress. For each i, contestant i has already scored day2scores[i] points. (Thus, their final score for day 2 will be at least equal to this value.)
The maximum number of points that can be scored on each contest day is 300.
The final ranking is made by sorting the contestants according to the total number of points they scored (on day 1 plus on day 2). The winner has rank 1. If multiple contestants are tied, they all share the smallest of the ranks they occupy in the ranking. Formally, the rank of contestant i can be computed as 1 plus the number of contestants who have a strictly higher point total than contestant i.
In the situation described by the current standings, the guaranteed final rank of contestant i, denoted G[i], is the smallest integer such that it is guaranteed that the final rank of contestant i will not exceed G[i].
Compute and return G. That is, the return value of your function is a sequence of N values: { G[0], G[1], ..., G[N-1] }.
Constraints
- N will be between 1 and 400, inclusive.
- day1scores will have exactly N elements.
- day2scores will have exactly N elements.
- Each element of day1scores and day2scores will be between 0 and 300, inclusive.
Examples
0)
4
{0, 300, 0, 0}
{0, 0, 0, 0}
Returns: {4, 1, 4, 4 }
During day 1 contestant 1 got the full 300 points while everyone else got zero. Day 2 just began, nobody has any points yet. As the maximum for this day is again 300, all other contestants can only tie contestant 1, and thus contestant 1 is guaranteed to be first. Each of the other contestant is only guaranteed rank 4 because it is still possible that in the end they will be the only one with the smallest total score.
1)
8
{300, 300, 200, 200, 100, 100, 0, 0}
{270, 270, 270, 270, 270, 270, 270, 270}
Returns: {2, 2, 4, 4, 6, 6, 8, 8 }
Based on the current scores we know that contestants 0 and 1 will end on rank 2 or better, contestants 2 and 3 will end on rank 4 or better, contestants 4 and 5 cannot be worse than in 6th place, and contestants 6 and 7 can still be last alone.
2)
4
{300, 200, 100, 100}
{107, 204, 300, 300}
Returns: {2, 2, 3, 3 }
Contestants 2 and 3 are guaranteed to be tied for third place with a final score of 400 points.
3)
400
{180, 32, 220, 283, 232, 292, 175, 131, 262, 197, 200, 20, 214, 12, 52, 0, 135, 246, 279, 4, 161, 290, 218, 117, 121, 267, 263, 183, 226, 123, 17, 287, 191, 180, 175, 285, 294, 100, 122, 18, 64, 170, 50, 185, 296, 196, 260, 276, 129, 49, 116, 171, 111, 241, 56, 213, 180, 146, 122, 284, 133, 182, 272, 289, 20, 247, 159, 288, 202, 133, 265, 113, 58, 106, 194, 248, 129, 285, 76, 227, 7, 87, 280, 42, 38, 136, 261, 279, 243, 223, 187, 16, 135, 264, 241, 161, 11, 295, 124, 108, 177, 220, 94, 90, 240, 101, 65, 50, 69, 291, 176, 270, 200, 55, 136, 227, 0, 62, 212, 34, 189, 10, 135, 21, 71, 92, 261, 251, 102, 253, 270, 232, 288, 290, 5, 37, 89, 77, 278, 173, 23, 120, 31, 193, 63, 11, 45, 154, 27, 280, 157, 122, 273, 77, 281, 296, 139, 292, 41, 288, 251, 175, 284, 26, 58, 211, 213, 181, 155, 288, 250, 71, 32, 260, 59, 236, 232, 9, 222, 288, 267, 33, 147, 250, 257, 58, 125, 180, 169, 85, 236, 11, 300, 50, 235, 235, 141, 278, 12, 286, 96, 146, 20, 134, 277, 247, 196, 35, 55, 266, 244, 275, 185, 296, 159, 210, 104, 46, 52, 262, 156, 207, 170, 275, 184, 55, 47, 218, 184, 25, 179, 298, 28, 200, 137, 130, 107, 148, 107, 238, 153, 227, 225, 162, 28, 79, 297, 245, 0, 14, 216, 234, 266, 224, 131, 150, 52, 155, 63, 86, 216, 172, 254, 218, 120, 257, 291, 262, 134, 160, 284, 11, 194, 236, 285, 91, 193, 21, 92, 92, 39, 248, 210, 30, 114, 236, 90, 203, 2, 71, 37, 286, 199, 0, 196, 255, 233, 191, 62, 261, 205, 52, 44, 215, 210, 281, 53, 89, 255, 243, 224, 47, 202, 268, 258, 167, 221, 100, 161, 203, 38, 67, 249, 170, 53, 129, 248, 47, 182, 15, 202, 41, 114, 264, 107, 259, 131, 156, 256, 58, 287, 31, 146, 90, 249, 123, 207, 242, 3, 204, 120, 283, 191, 54, 172, 32, 80, 54, 122, 93, 40, 72, 263, 86, 84, 39, 47, 64, 201, 178, 62, 212, 150, 281, 112, 177, 46, 160, 52, 18, 103, 286, 69, 169, 46, 163, 219, 259, 279, 293, 180, 266, 265, 217, 224, 223, 211, 251, 11, 99}
{167, 25, 219, 51, 224, 298, 63, 49, 171, 223, 30, 170, 95, 209, 240, 265, 243, 264, 61, 117, 101, 13, 276, 252, 166, 72, 83, 148, 37, 24, 152, 22, 3, 131, 176, 98, 284, 110, 189, 189, 68, 103, 229, 17, 154, 153, 215, 56, 216, 214, 177, 254, 131, 23, 289, 251, 117, 138, 207, 29, 12, 201, 97, 213, 187, 266, 45, 176, 173, 225, 34, 33, 242, 136, 32, 83, 104, 116, 216, 241, 101, 151, 3, 58, 288, 6, 128, 273, 109, 272, 190, 241, 109, 170, 205, 19, 300, 212, 166, 275, 176, 3, 55, 10, 159, 24, 111, 268, 1, 17, 283, 25, 196, 237, 97, 45, 141, 202, 261, 178, 19, 33, 155, 159, 26, 226, 237, 208, 170, 46, 129, 215, 191, 50, 193, 193, 90, 151, 15, 15, 294, 295, 97, 64, 287, 114, 44, 3, 216, 218, 213, 216, 296, 65, 78, 192, 275, 235, 134, 75, 38, 20, 123, 300, 65, 36, 8, 70, 62, 265, 65, 149, 291, 214, 280, 249, 297, 12, 85, 277, 296, 74, 118, 60, 77, 145, 247, 250, 235, 158, 209, 230, 93, 6, 219, 249, 250, 208, 175, 191, 284, 154, 157, 201, 192, 18, 269, 137, 72, 239, 200, 51, 55, 17, 188, 174, 292, 75, 0, 133, 179, 81, 20, 211, 246, 165, 75, 136, 131, 169, 209, 57, 105, 90, 118, 144, 125, 235, 270, 174, 79, 270, 184, 57, 74, 90, 289, 116, 276, 292, 270, 164, 277, 105, 127, 20, 187, 194, 88, 250, 87, 98, 206, 27, 240, 167, 280, 276, 38, 132, 48, 70, 263, 296, 106, 140, 199, 56, 130, 283, 183, 61, 192, 190, 272, 115, 148, 128, 164, 291, 19, 106, 151, 228, 166, 58, 74, 93, 133, 175, 140, 48, 150, 106, 19, 138, 111, 101, 252, 253, 39, 195, 11, 76, 54, 214, 154, 112, 211, 97, 44, 109, 114, 280, 45, 284, 214, 158, 161, 191, 60, 46, 160, 232, 108, 60, 44, 274, 174, 290, 247, 112, 30, 163, 157, 194, 135, 30, 38, 131, 234, 258, 112, 262, 261, 248, 145, 163, 223, 264, 127, 168, 292, 107, 292, 90, 96, 122, 21, 15, 260, 133, 150, 101, 175, 286, 172, 258, 88, 167, 190, 94, 80, 252, 38, 18, 200, 237, 230, 150, 48, 252, 138, 170, 144, 111, 218, 38, 130, 195}
Returns: {337, 400, 229, 357, 215, 13, 400, 400, 238, 256, 400, 400, 390, 400, 400, 400, 297, 144, 349, 400, 400, 394, 165, 304, 400, 350, 341, 362, 400, 400, 400, 390, 400, 384, 333, 295, 42, 400, 384, 400, 400, 400, 400, 400, 221, 336, 192, 359, 344, 400, 400, 247, 400, 400, 344, 205, 400, 400, 365, 382, 400, 295, 304, 153, 400, 138, 400, 205, 300, 316, 400, 400, 396, 400, 400, 362, 400, 274, 400, 204, 400, 400, 400, 400, 368, 400, 288, 82, 328, 165, 297, 400, 400, 236, 225, 400, 385, 147, 400, 295, 326, 400, 400, 400, 277, 400, 400, 376, 400, 391, 212, 400, 278, 400, 400, 400, 400, 400, 195, 400, 400, 400, 400, 400, 400, 376, 161, 212, 400, 400, 277, 224, 187, 349, 400, 400, 400, 400, 400, 400, 378, 261, 400, 400, 333, 400, 400, 400, 400, 161, 304, 352, 52, 400, 315, 173, 261, 115, 400, 310, 400, 400, 267, 369, 400, 400, 400, 400, 400, 81, 380, 400, 370, 195, 350, 174, 115, 400, 391, 58, 62, 400, 400, 389, 357, 400, 300, 243, 271, 400, 228, 400, 280, 400, 219, 176, 284, 174, 400, 189, 295, 396, 400, 356, 202, 400, 205, 400, 400, 149, 228, 368, 400, 382, 337, 294, 278, 400, 400, 279, 356, 400, 400, 174, 243, 400, 400, 324, 380, 400, 290, 321, 400, 400, 400, 400, 400, 295, 297, 264, 400, 161, 266, 400, 400, 400, 23, 315, 400, 392, 174, 278, 97, 365, 400, 400, 400, 336, 400, 356, 394, 400, 210, 400, 315, 248, 50, 103, 400, 400, 359, 400, 214, 112, 284, 400, 281, 400, 400, 300, 400, 390, 273, 400, 291, 333, 400, 362, 400, 312, 400, 281, 333, 400, 312, 382, 391, 400, 400, 231, 344, 400, 400, 371, 400, 259, 400, 400, 147, 162, 400, 400, 400, 345, 382, 295, 300, 400, 300, 396, 400, 400, 310, 221, 400, 263, 206, 400, 346, 400, 400, 400, 400, 162, 400, 376, 400, 243, 243, 337, 110, 400, 400, 400, 270, 378, 346, 400, 400, 356, 324, 100, 394, 379, 238, 400, 400, 400, 344, 320, 400, 400, 78, 400, 299, 400, 400, 400, 400, 400, 371, 344, 396, 295, 400, 205, 400, 259, 400, 400, 400, 295, 400, 255, 400, 400, 259, 162, 147, 228, 400, 130, 272, 290, 306, 357, 244, 400, 400, 400 }
4)
400
{165, 235, 149, 82, 123, 93, 185, 117, 158, 18, 110, 294, 242, 12, 182, 4, 145, 140, 283, 212, 271, 120, 232, 232, 27, 42, 66, 206, 226, 95, 126, 23, 205, 231, 272, 268, 51, 285, 13, 278, 229, 276, 248, 82, 81, 122, 141, 163, 99, 285, 252, 260, 140, 235, 130, 172, 268, 59, 113, 130, 115, 16, 70, 125, 229, 43, 165, 280, 110, 165, 48, 133, 265, 80, 142, 184, 71, 84, 40, 94, 28, 260, 91, 284, 52, 146, 21, 164, 94, 44, 230, 141, 50, 152, 100, 253, 73, 69, 124, 275, 123, 159, 131, 232, 13, 158, 96, 13, 220, 89, 137, 249, 96, 229, 6, 189, 126, 205, 259, 91, 90, 91, 25, 110, 161, 206, 153, 137, 47, 155, 117, 22, 287, 241, 156, 120, 151, 233, 91, 90, 283, 155, 235, 148, 149, 26, 157, 19, 35, 204, 290, 259, 217, 74, 193, 196, 277, 114, 271, 286, 211, 227, 276, 93, 129, 205, 164, 171, 63, 193, 222, 71, 45, 222, 127, 120, 1, 131, 277, 12, 172, 203, 272, 155, 101, 129, 34, 25, 124, 89, 180, 177, 42, 255, 133, 143, 188, 104, 24, 133, 249, 119, 55, 270, 156, 94, 203, 143, 103, 270, 143, 82, 82, 163, 78, 142, 246, 50, 146, 133, 77, 200, 112, 113, 91, 44, 148, 264, 74, 238, 151, 16, 54, 284, 113, 106, 54, 100, 255, 196, 154, 130, 6, 171, 184, 215, 49, 45, 168, 133, 273, 118, 297, 70, 125, 254, 282, 102, 17, 85, 12, 291, 160, 116, 187, 117, 125, 250, 189, 103, 217, 95, 237, 113, 18, 208, 238, 118, 216, 9, 216, 262, 33, 251, 99, 200, 96, 1, 122, 252, 266, 6, 281, 151, 245, 160, 156, 265, 258, 192, 113, 27, 111, 111, 251, 225, 255, 204, 278, 205, 71, 214, 182, 6, 268, 173, 279, 54, 185, 261, 197, 134, 78, 27, 110, 27, 288, 134, 132, 90, 191, 191, 118, 292, 296, 283, 68, 120, 54, 68, 184, 26, 74, 89, 199, 138, 267, 32, 272, 78, 123, 164, 232, 265, 134, 48, 179, 131, 4, 283, 142, 273, 137, 238, 268, 239, 77, 186, 69, 106, 10, 50, 27, 196, 252, 105, 270, 294, 80, 188, 29, 285, 93, 281, 122, 246, 245, 218, 29, 254, 119, 262, 294, 166, 261, 112, 198, 233, 69, 86}
{87, 101, 170, 0, 267, 102, 280, 229, 83, 149, 267, 222, 241, 283, 223, 10, 85, 298, 219, 204, 16, 285, 25, 31, 52, 106, 246, 96, 282, 16, 273, 61, 8, 169, 132, 245, 142, 50, 59, 183, 247, 4, 142, 292, 235, 228, 95, 63, 132, 188, 238, 27, 251, 16, 218, 41, 107, 189, 100, 117, 299, 73, 105, 253, 263, 54, 148, 276, 50, 250, 99, 19, 76, 259, 132, 75, 143, 190, 75, 170, 272, 189, 65, 73, 219, 208, 292, 162, 92, 192, 9, 53, 217, 85, 33, 51, 66, 52, 39, 111, 14, 92, 197, 49, 32, 285, 246, 8, 62, 88, 170, 67, 67, 142, 114, 71, 26, 198, 81, 214, 283, 14, 37, 124, 257, 218, 260, 32, 181, 124, 182, 136, 96, 22, 156, 22, 90, 30, 268, 159, 157, 223, 174, 24, 188, 128, 93, 266, 83, 97, 12, 272, 238, 117, 132, 213, 245, 2, 26, 174, 208, 47, 38, 175, 106, 132, 175, 61, 77, 230, 193, 297, 172, 103, 131, 140, 234, 127, 246, 90, 294, 209, 198, 101, 18, 165, 22, 120, 34, 59, 140, 122, 246, 225, 71, 49, 4, 300, 170, 145, 291, 20, 135, 191, 190, 186, 80, 45, 131, 45, 247, 274, 259, 239, 174, 198, 83, 151, 61, 228, 216, 299, 135, 127, 123, 23, 80, 17, 156, 214, 253, 126, 108, 28, 139, 296, 297, 108, 263, 19, 164, 140, 68, 213, 61, 59, 116, 271, 91, 92, 56, 200, 165, 137, 3, 256, 273, 139, 90, 261, 4, 263, 157, 293, 152, 209, 294, 298, 191, 169, 125, 144, 109, 172, 206, 190, 108, 70, 181, 263, 14, 237, 75, 279, 180, 202, 45, 44, 37, 284, 214, 258, 78, 94, 86, 231, 35, 109, 187, 196, 98, 254, 36, 285, 254, 101, 28, 10, 165, 287, 99, 194, 6, 70, 284, 201, 188, 118, 55, 127, 102, 197, 131, 236, 202, 215, 247, 17, 84, 79, 99, 181, 272, 179, 75, 24, 18, 65, 94, 91, 25, 6, 182, 107, 11, 259, 68, 15, 175, 129, 154, 212, 73, 229, 227, 82, 81, 271, 218, 6, 65, 92, 251, 64, 213, 189, 12, 4, 297, 234, 104, 154, 85, 142, 264, 156, 212, 94, 164, 51, 299, 188, 283, 114, 107, 234, 227, 95, 115, 140, 12, 49, 202, 24, 186, 290, 31, 224, 19, 54}
Returns: {400, 358, 378, 400, 298, 400, 163, 350, 400, 400, 317, 110, 151, 400, 272, 400, 400, 207, 127, 254, 400, 272, 400, 400, 400, 400, 387, 398, 116, 400, 280, 400, 400, 278, 273, 114, 400, 358, 400, 171, 156, 400, 298, 319, 382, 343, 400, 400, 400, 156, 140, 400, 293, 400, 347, 400, 319, 400, 400, 400, 256, 400, 400, 314, 137, 400, 384, 61, 400, 255, 400, 400, 357, 358, 400, 400, 400, 400, 400, 400, 400, 190, 400, 336, 400, 337, 384, 370, 400, 400, 400, 400, 400, 400, 400, 396, 400, 400, 400, 304, 400, 400, 364, 400, 400, 197, 355, 400, 400, 400, 392, 382, 400, 323, 400, 400, 400, 274, 357, 396, 322, 400, 400, 400, 248, 234, 257, 400, 400, 400, 400, 400, 307, 400, 387, 400, 400, 400, 335, 400, 205, 314, 270, 400, 358, 400, 400, 400, 400, 398, 398, 96, 181, 400, 372, 270, 104, 400, 400, 172, 246, 400, 384, 400, 400, 358, 358, 400, 400, 236, 255, 331, 400, 372, 400, 400, 400, 400, 104, 400, 162, 262, 161, 400, 400, 400, 400, 400, 400, 400, 378, 400, 400, 153, 400, 400, 400, 274, 400, 400, 82, 400, 400, 171, 350, 400, 400, 400, 400, 384, 298, 336, 357, 276, 400, 357, 362, 400, 400, 335, 400, 129, 400, 400, 400, 400, 400, 400, 400, 186, 273, 400, 400, 387, 400, 276, 342, 400, 107, 400, 379, 400, 400, 306, 400, 400, 400, 382, 400, 400, 362, 379, 171, 400, 400, 116, 61, 400, 400, 350, 400, 64, 381, 270, 358, 370, 246, 75, 312, 400, 355, 400, 350, 400, 400, 282, 350, 400, 282, 400, 400, 129, 400, 97, 400, 276, 400, 400, 400, 87, 153, 400, 335, 400, 362, 293, 400, 319, 196, 304, 400, 400, 400, 282, 119, 370, 400, 400, 197, 137, 400, 270, 400, 400, 67, 319, 162, 400, 400, 304, 400, 362, 400, 400, 387, 400, 87, 400, 400, 400, 400, 323, 298, 159, 323, 392, 400, 400, 400, 400, 400, 400, 400, 400, 400, 282, 358, 400, 194, 400, 400, 319, 396, 135, 335, 400, 400, 276, 400, 400, 400, 334, 304, 398, 153, 228, 400, 400, 333, 357, 400, 400, 400, 358, 110, 400, 151, 304, 400, 400, 364, 156, 319, 285, 400, 153, 157, 384, 400, 287, 400, 390, 132, 400, 194, 276, 400, 177, 400, 400 }
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class IOIGuaranteedPlace with a public method vector<int> solve(int N, vector<int> day1scores, vector<int> day2scores) · 58 test cases · 2 s / 256 MB per case