Game - MarisaOJ: Marisa Online Judge

Game

Time limit: 1000 ms
Memory limit: 256 MB
The given problem describes a game with $n$ levels, each on a different map. For each level, a player selects a car from three types: `A`, `B`, and `C`. There are four types of maps denoted by the characters `x`, `a`, `b`, and `c`. Some restrictions apply, such as not using car `A` for map `a`, not using car `B` for map `b`, and not using car `C` for map `c`. However, all three types of cars can be used for map `x`. The maps for each level are represented by a lowercase string. For example, $S = "xaabxcbc"$ indicates there are 8 levels. Levels 1 and 5 can use all types of cars. Levels 2 and 3 cannot use car `A`, levels 4 and 7 cannot use car `B`, and levels 6 and 8 cannot use car `C`. There are also $m$ constraints of the form $i, h_i, j, h_j$, meaning that if car $h_i$ is used in level $i$, then car $h_j$ must be used in level $j$. The task is to find a way to use cars for $n$ levels. If multiple solutions exist, any solution can be printed. If no solution is possible, print `-1`. ### Input - The first line consists of two non-negative integers $n,d$, where $d$ is the maximum number of levels with the map `x`. - The second line is the string $S$ representing the maps for each level. - The third line is an integer $m$ indicating the number of constraints. - The next $m$ lines, each containing four integers $i, h_i, j, h_j$. ### Output - Print a string of length $n$ representing the types of cars to be used. If no solution exists, print `-1`. ### Example Input: ``` 3 1 xcc 1 1 A 2 B ``` Output: ``` ABA ``` ### Constraints
Test Point Number n d m Other Properties
1 $ \leq 2 $ 0 $ \leq 4 $ None
2 $ \leq n $
3 $ \leq 5 $ 0 $ \leq 10 $
4 $ \leq n $
5 $ \leq 10 $ 0 $ \leq 20 $
6 $ \leq 8 $
7 $ \leq 20 $ 0 $ \leq 40 $ S contains only c
8 None
9 $ \leq 8 $ S contains only x or c
10 None
11 $ \leq 100 $ 0 $ \leq 200 $ S contains only c
12 None
13 $ \leq 8 $ S contains only x or c
14 None
15 $ \leq 5 \times 10^3 $ 0 $ \leq 10^4 $
16 $ \leq 8 $ S contains only x or c
17 None
18 $ \leq 5 \times 10^4 $ 0 $ \leq 10^5 $
19 $ \leq 8 $ S contains only x or c
20 None