| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11617 | pA - Arranging a Sequence |
|
| 12022 | prefix sum |
|
| 12441 | Palindrome |
|
| 14435 | Orange Cat's Puzzle |
|
Description
Source : ACM International Collegiate Programming Contest Asia Regional Contest, Tsukuba, 2016/10/16
You are given an ordered sequence of integers, (1,2,3,...,n). Then, a number of requests will be given. Each request specifes an integer in the sequence. You need to move the specied integer to the head of the sequence, leaving the order of the rest untouched. Your task is to find the order of the elements in the sequence after following all the requests successively.
Sample Output Explanation : In Sample Input 1, the initial sequence is (1; 2; 3; 4; 5). The first request is to move the integer 4 to the head, that is, to change the sequence to (4; 1; 2; 3; 5). The next request to move the integer 2 to the head makes the sequence (2; 4; 1; 3; 5). Finally, 5 is moved to the head, resulting in (5; 2; 4; 1; 3).
Input
The input consists of a single test case of the following form.
n m
e1
:
em
The integer n is the length of the sequence ( 1 <= n <= 200000 ). The integer m is the number of requests ( 1 <= m <= 100000 ). The following m lines are the requests, namely e1,...,em, one per line. Each request ei ( 1 <= i <= m ) is an integer between 1 and n, inclusive, designating the element to move. Note that, the integers designate the integers themselves to move, not their positions in the sequence.
Output
Output the sequence after processing all the requests. Its elements are to be output, one per line, in the order in the sequence.
There should be a new line at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a series of numbers, e1, e2, e3, ..., eN.
With these numbers, we want to know what the sum is in some consecutive range.
In every testcase, you will be given M queries.
Each of them contains two integers which represent left bound (L) and right bound (R) respectively.
Your mission is to give the result of eL + eL+1 + ... + eR,
-
Hint 0 : If you get WA for testcase 1, sample input and output might help you.
Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".
A usual computer can run 109 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 108 operations (+, -, *, /, =, ...) in 1 second)!
Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.
Input
First line contains one integer N which is the size of elements.
Second line will have N integers representing all elements in the testcase.
Third line contains one integer M which is the number of queries.
For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.
It is guaranteed that:
1. 10 ≦ N ≦ 1,000,000
2. 0 ≦ ei ≦ 100,000, for 1 ≦ i ≦ N
3. L must be less than or equal to R, and R won't exceed the size of elements.
Output
For each query, just give the answer in one line.
Also, remember to print '\n' in the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Check whether a given string is a palindrome or not.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000. The number of test case is less than 1000.
Output
For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Orange Cat（橘貓） loves playing with puzzles. Each puzzle consists of 26 letters, from a to z, and can be represented as a string.
When assembling the puzzles, Orange Cat refers to his instruction manuals. However, he accidentally mixed up the numbers of these instruction manuals. He had to arrange them randomly, but he can't determine if his arrangement is correct. Please write a program to tell him which instruction manuals correctly correspond to their respective puzzles.
The definition of an instruction manual correctly corresponding to a puzzle is: two strings can become the same after any rearrangement. For example, if Orange Cat matches the puzzle "abc" with an instruction manual containing "cba", then this correspondence is correct.
Input
The first line of input contains an integer n. n represents the number of puzzle-instruction manual pairs.
The following n lines each contain two strings, Ai and Bi, separated by a space. They represent the i-th puzzle and instruction manual, respectively.
Constraints
- 1 ≤ n ≤ 500
- All strings are composed of lowercase English letters.
- 1 ≤ | Ai | = | Bi | ≤ 10000 (| S | represents the length of string S)
Subtasks
- Testcases 1: n = 1
- Testcases 2 ~ 3: Characters within Ai , Bi are arranged in ascending lexicographic order.
- Testcases 4 ~ 6: No additional restrictions.
Important: The method for comparing the lexicographic order of two strings is as follows: Starting from the first position (leftmost), find the first character that differs. The string with the smaller character at that position is considered lexicographically smaller. For example, 'abc' < 'abd' because the first differing letter 'c' < 'd'.
Output
Output a single integer representing the number of puzzle and instruction manual pairs that Orange Cat correctly matched.
Please remember to print "\n" at the end.