codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1910B.md (2294B)


      1 Source: https://codeforces.com/problemset/problem/1910/B
      2 
      3 B. Security Guard
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Monocarp is a security guard in Berland State University. Every day, he tracks how many people and at what time enter and leave the university. He writes this information down as follows:
     22 
     23 * when someone enters the university, Monocarp writes a plus sign '+';
     24 * when someone leaves the university, Monocarp writes a minus sign '-'.
     25 
     26 At the beginning of the current day, there are no people at the university, except for Monocarp. During the day, Monocarp wrote out a sequence $s$. The characters in $s$ are listed in the order Monocarp wrote them.
     27 
     28 Suddenly, Monocarp's boss decided to check his work. Unfortunately, Monocarp is a bit careless. So, the sequence $s$ that he wrote might be impossible. For example, the sequence "+--" can't happen, since it represents a scenario when one person enters the university and two leave.
     29 
     30 Before his boss starts checking the sequence, Monocarp has the time to swap at most one pair of characters in it. Can he do it in such a way that the resulting sequence is plausible? Note that if the given sequence is already plausible, Monocarp doesn't have to swap anything.
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     35 
     36 The only line of each test case contains a single string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting only of characters '+' and/or '-'. A plus sign '+' represents a person entering the university. A minus sign '-' represents a person leaving the university.
     37 
     38 The sum of all $|s|$ over all test cases doesn't exceed $3 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, print an answer.
     43 
     44 If it's impossible to swap at most one pair of characters so that the resulting sequence is plausible, print -1.
     45 
     46 Otherwise, print two integers. If you swap one pair of characters, print two distinct integers from $1$ to $n$ — the indices of characters to swap. If you don't swap, print one integer from $1$ to $n$ twice — swap a character with itself.
     47 
     48 If there are multiple answers, print any of them.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 6
     56 
     57 -+
     58 
     59 +-
     60 
     61 +++-
     62 
     63 ---++
     64 
     65 +
     66 
     67 -
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 1 2
     74 1 1
     75 1 1
     76 -1
     77 1 1
     78 -1
     79 ```