시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 256 MB | 37 | 17 | 12 | 60.000% |
In college football, many different sources create a list of the Top 25 teams in the country. Since it’s subjective, these lists often differ, but they’re usually very similar. Your job is to compare two of these lists, and determine where they are similar. In particular, you are to partition them into sets, where each set represents the same consecutive range of positions in both lists, and has the same teams, and is as small as possible. If the lists agree completely, you’ll have 25 lists (or n, where n is an input). For these lists:
K&R Poll | Lovelace Ranking |
---|---|
A | A |
B | C |
C | D |
D | B |
E | E |
You’ll have 3 sets:
A B C D E
The input will start with a single integer on one line giving the number of test cases. There will be at least one but not more than 100 test cases. Each test case will begin with an integer N, 1 ≤ N ≤ 1,000,000, indicating the number of teams ranked. The next N lines will hold the first list, in order. The team names will appear one per line, consist of at most 8 capital letters only. After this will be N lines, in the same format, indicating the second list. Both lists will contain the same team names, and all N team names will be unique.
For each test case, simply output the size of each set, in order, on one line, with the numbers separated by a single space. Do not output any extra spaces, and do not output blank lines between numbers.
3 5 A B C D E A C D B E 3 RED BLUE ORANGE RED BLUE ORANGE 3 MOE LARRY CURLY CURLY MOE LARRY
1 3 1 1 1 1 3