XorOrderDiv2
SRM 697 · 2016-07-09 · by Arterm
Problem Statement
Welcome to the Festival of Binary Numbers! The festival will last for 2^m days. The days are numbered 0 through 2^m - 1. On each day of the festival there is a single race. There are n contestants, numbered 0 through n-1. Each contestant takes part in all 2^m races.
You are given the
For each i and j, the time needed by contestant i to finish the race on day j can be computed as (a[i] xor j). Note that on each day the contestants' times will all be distinct. After each race the contestants are ordered according to the time they needed, starting with the fastest one. Contestant who places x-th (counting from zero) will get x^2 penalty points. (I.e., starting from the winner of the race, the contestants get 0, 1, 4, 9, 16, ... penalty points.) For each i, let p[i] be the total number of penalty points contestant i receives in the 2^m races.
Compute and return the
Constraints
- m will be between 1 and 30, inclusive.
- a will contain between 1 and 1,000 elements, inclusive.
- Each element in a will be between 0 and 2^m - 1, inclusive.
- All elements in a will be distinct.
2
{0,1,2}
Returns: {6, 6, 8 }
There are 2^2 = 4 days and 3 contestants. Their skill levels are a = {0, 1, 2}. The individual races are described below: day 0: finishing times are {0, 1, 2}, penalty points are {0, 1, 4}. day 1: finishing times are {1, 0, 3}, penalty points are {1, 0, 4}. day 2: finishing times are {2, 3, 0}, penalty points are {1, 4, 0}. day 3: finishing times are {3, 2, 1}, penalty points are {4, 1, 0}. Hence, the penalty point totals are {6, 6, 8}.
1
{1}
Returns: {0 }
5
{13,17}
Returns: {16, 16 }
2
{0,3,2}
Returns: {8, 6, 6 }
4
{12,10}
Returns: {8, 8 }
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class XorOrderDiv2 with a public method vector<long long> getExpectation(int m, vector<int> a) · 51 test cases · 2 s / 256 MB per case