WindowManager
SRM 200 · 2004-06-21 · by antimatter
Problem Statement
You are debugging a window manager for a GUI that uses a fixed character size, and a screen that is a rectangular grid of these characters. To that end, you are making it create various overlapping windows to test whether the display code works correctly.
The screen has width width and height height. Initially, each character in the screen is a space (' ', or ASCII value 32). The elements of windows represent the windows that you are creating, in order of their creation, where the earliest-created windows come first in windows. A window consists of a frame and a fill character, shown below:
+----+
|XXXX|
|XXXX|
+----+
The corners of the frame are '+', the top and bottom are '-', the left and right are '|', and the interior of the window is filled with some character (here 'X'). Each element in windows will be of the form "tlv tlh vs hs fill", where each field is separated by a single space. tlv and tlh will be 32-bit integers between -100000000 and 100000000, inclusive, representing the vertical and horizontal offsets from the top-left of the screen. A positive vertical offset is downwards, and a positive horizontal offset is to the right. vs and hs represent the vertical and horizontal size of the window, and will each be between 2 and 100000000, inclusive. fill represents the character that will go in the center of the window. Note that if vs, hs, or both are equal to 2, then the fill character does not appear because the frame takes up all the allotted space for the window. If the picture drawn earlier represented the entirety of the screen, then the window shown would be represented by the
If one window is created that would intersect another window, the later window will appear over the earlier window. That is, any part of the earlier-created window that intersects a later-created window is hidden. Windows may also be drawn partially or completely off-screen.
You wish to find what the window manager should show given some sequence of windows. Your method should return a
Constraints
- width will be between 1 and 100, inclusive
- height will be between 1 and 100, inclusive
- width * height will not exceed 8000.
- windows will contain between 1 and 50 elements, inclusive
- each element of windows will be of the form "tlv tlh vs hs fill" as explained in the problem statement
- tlv and tlh will be between -100000000 and 100000000, inclusive, with no leading zeros.
- vs and hs will be between 2 and 100000000, inclusive, with no leading zeros.
- fill will be an ASCII character with value between 33 and 126, inclusive, that is also not '+', '-', or '|'
4
6
{"-5 -5 20 20 O", "0 0 2 2 Y", "0 0 4 6 X"}
Returns: { "+----+", "|XXXX|", "|XXXX|", "+----+" }
+----+ |XXXX| |XXXX| +----+ A full-screen window completely covering up two others.
7
7
{"-5 -5 20 12 9", "2 2 15 15 @", "2 2 3 3 *"}
Returns: { "999999|", "999999|", "99+-+--", "99|*|@@", "99+-+@@", "99|@@@@", "99|@@@@" }
5
7
{"-5 -5 7 7 A", "-1 5 3 3 I", "1 -1 3 3 M", "1 5 3 3 A",
"3 -1 3 3 T", "3 1 3 3 T", "3 3 3 3 E", "-1 1 3 3 N", "3 5 3 3 R", "-1 3 3 3 T"}
Returns: { "A|N|T|I", "-+-+-+-", "M| |A", "-+-+-+-", "T|T|E|R" }
1
1
{"-20000 -20000 5 5 X"}
Returns: { " " }
Note two things: windows may be completely off-screen, and the default character for any grid location is a space.
23
75
{"-44 -128 10 36 i","-21 134 36 82 }","-16 55 29 138 L","-11 -58 26 83 V","8 35 36 32 E","-1 104 43 82 7","-33 121 46 98 C","41 83 47 26 V","-28 107 4 101 p","44 45 39 98 v","-32 -44 32 46 d","29 -141 25 81 ,","26 40 22 42 z","-41 -116 14 108 Y"}
Returns: { "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |LLLLLLLLLLLLLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| +------------------------------+LLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE|LLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE|LLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE|LLLLLLLL", "VVVVVVVVVVVVVVVVVVVVVVVV| |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE|--------", "VVVVVVVVVVVVVVVVVVVVVVVV| |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", "------------------------+ |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| ", " |EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE| " }
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WindowManager with a public method vector<string> screen(int height, int width, vector<string> windows) · 63 test cases · 2 s / 256 MB per case