PaintByPatterns
2019 TCC India Final · 2019-05-04 · by misof
Problem Statement
This problem has a nonstandard time limit: 4 seconds.
There is an infinite white bitmap. You are supposed to execute a series of n instructions. Each instruction will paint some of the pixels of the bitmap black. Your task is to count and return the number of black pixels at the end of the whole process.
Each instruction has five arguments: x1, y1, x2, y2, and p. The first four values are coordinates; they satisfy x1 <= x2 and y1 <= y2. The value p is a 16-bit integer that is interpreted as a 4x4 boolean array P in x-major order: P[x,y] corresponds to the bit 4*x+y of p (with bit 0 being the least significant bit of p). For example, p=2^8 represents an array in which only P[2,0] is true and all other cells are false.
The instruction repeatedly prints the pattern described by P onto the rectangle described by the other four arguments. In particular, the instruction is executed as follows:
xsize = x2 - x1 + 1
ysize = y2 - y1 + 1
for dx = 0 .. xsize-1:
for dy = 0 .. ysize-1:
if P[dx mod 4, dy mod 4]:
paint the pixel (x1 + dx, y1 + dy) black
The first length(x1) instructions are given in the
state = (state * 1103515245 + 12345) mod 2^31 x1 = state state = (state * 1103515245 + 12345) mod 2^31 y1 = state state = (state * 1103515245 + 12345) mod 2^31 x2 = state state = (state * 1103515245 + 12345) mod 2^31 y2 = state state = (state * 1103515245 + 12345) mod 2^31 p = state mod 2^16 if x1 > x2: swap(x1,x2) if y1 > y2: swap(y1,y2) execute the instruction with parameters x1, y1, x2, y2, p
Constraints
- n will be between 1 and 2,000, inclusive.
- x1 will have between 0 and min(n,200) elements, inclusive.
- y1, x2, y1, and p will each have the same number of elements as x1.
- For each valid i: 0 <= x1[i] <= x2[i] <= (2^31)-1.
- For each valid i: 0 <= y1[i] <= y2[i] <= (2^31)-1.
- For each valid i: p[i] will be between 0 and (2^16)-1, inclusive.
- seed will be between 0 and (2^31)-1, inclusive.
1
{10}
{20}
{30}
{50}
{65535}
47
Returns: 651
The value p[0] represents a full bitmap, hence the instruction will paint its entire rectangle black. The rectangle is formed by pixels (x,y) such that 10 <= x <= 30 and 20 <= y <= 50. Hence, the rectangle consists of 21 * 31 = 651 black pixels.
2
{10, 0}
{20, 30}
{30, 40}
{50, 40}
{65535, 65535}
47
Returns: 871
Two overlapping black rectangles.
2
{10, 0}
{20, 30}
{30, 40}
{50, 40}
{42405, 42405}
47
Returns: 436
Two overlapping rectangles with the same checkerboard pattern.
2
{10, 0}
{20, 30}
{30, 40}
{50, 40}
{42405, 23130}
47
Returns: 551
The same two rectangles but now one uses the opposite checkerboard pattern.
3
{}
{}
{}
{}
{}
474747
Returns: 848809312519167942
Three large random rectangles. Their values (x1,y1,x2,y2,p) are as follows: 1353942 1069631319 1178682520 1916843249 4676 44630515 9075810 1377480493 1434455728 4393 55535068 1040160485 429391022 1363659343 13754
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PaintByPatterns with a public method long long countBlack(int n, vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2, vector<int> p, int seed) · 77 test cases · 2 s / 256 MB per case