9/13/25, 4:11 AM Problem - E - Codeforces
Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 1045 (Div. 2)
E. Power Boxes Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Practice?
This is an interactive problem. Want to solve the contest problems after the
official contest ends? Just register for
practice and you will be able to submit
You are given n boxes, indexed from 1 to n. The boxes look identical, but each one has a hidden solutions.
power value ai , which is either 1 or 2.
Register for practice
You want to determine the power value of each box. To do so, you conduct the following
experiment. Initially, the i -th box is placed at coordinate i on a number line (1 ≤ i ≤ n ).
→ Virtual participation
You are allowed to perform the following two types of queries:
Virtual contest is a way to take part in past
"swap x " (1 ≤ x ≤ n − 1 ): Swap the boxes currently located at coordinates x and contest, as close as possible to participation
on time. It is supported only ICPC mode for
x + 1. Note that this change is permanent and affects all subsequent queries. virtual contests. If you've seen these
"throw x " (1 ≤ x ≤ n): Throw a ball at the box located at coordinate x . The ball travels problems, a virtual contest is not for you -
solve these problems in the archive. If you
p units forward to coordinate x + p if the power value of the box is p. If there is a box at the just want to solve some problem from a
contest, a virtual contest is not for you -
new coordinate, the ball jumps again using the power of that box. This continues until the ball solve this problem in the archive. Never use
lands on a coordinate without a box. As a response, you are given the total number of jumps someone else's code, read the tutorials or
communicate with other person during a
the ball made before stopping. virtual contest.
Your task is to determine the power value of each box using no more than ⌈
3n
⌉ queries in total, Start virtual contest
2
counting both swap and throw queries.
Input → Problem tags
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 500 ). The description of the test cases follows.
constructive algorithms dp
implementation interactive *2300
The first and the only line of each test case contains a single integer n (2 ≤ n ≤ 1000 ) — the No tag edit access
number of boxes.
It is guaranteed that the sum of n over all test cases does not exceed 1000 . → Contest materials
Interaction Announcement (en)
The interaction for each test case begins by reading the integer n.
Tutorial (en)
To make a query, output a line in one of the following formats:
"swap x " (without quotes) (1 ≤ x ≤ n − 1 ): Swap the boxes currently located at
coordinates x and x + 1.
"throw x " (without quotes) (1 ≤ x ≤ n ): Throw a ball at the box located at coordinate x .
The jury will respond with an integer representing the number of jumps the ball made before
stopping.
Note that queries are case sensitive.
Once you have determined the power value of each box, output a line in the following format:
"! a1 a2 … an " (without quotes): Here, ai is the power value of the box initially located at
coordinate i (1 ≤ i ≤ n ). After submitting the final answer, proceed on to the next test
case.
Note that submitting the final answer with the previous query does not count towards the limit of
3n
⌈
2
⌉ queries.
If your program exceeds ⌈ 3n
2
⌉ queries in one test case, your program must terminate
immediately to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
After outputting a query, do not forget to output the end of the line and flush the output.
Otherwise, you will get Idleness limit exceeded. To do this, use:
https://codeforces.com/contest/2134/problem/E 1/3
9/13/25, 4:11 AM Problem - E - Codeforces
fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
sys.stdout.flush() in Python;
std::io::stdout().flush() in Rust;
see the documentation for other languages.
The interactor is non-adaptive; the power values of the boxes remain constant throughout the
interaction.
Hacks
To hack, use the following format.
The first line should contain a single integer t (1 ≤ t ≤ 500 ) — the number of test cases.
The first line of each test case contains a single integer n (2 ≤ n ≤ 1000 ) — the number of
boxes.
The second line of each test case contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 2 ) — the
power value of each box.
The sum of n over all test cases should not exceed 1000 .
Example
input Copy
2
4
output Copy
throw 2
swap 3
throw 2
throw 1
! 2 1 2 1
throw 1
swap 1
throw 1
! 1 2
Note
Below is the interaction process in the example:
Solution Jury Explanation
2 There are 2 test cases.
There are 4 boxes in the first test case. The hidden power values are
4
a = [2, 1, 2, 1] .
throw Throw a ball at the box located at coordinate 2. The ball travels through
2
2 coordinates 2 → 3 → 5 and stops at coordinate 5, so the response is 2.
Swap the boxes located at coordinate 3 and 4. Now box 3 is located at
swap 3
coordinate 4 and box 4 is located at coordinate 3.
https://codeforces.com/contest/2134/problem/E 2/3
9/13/25, 4:11 AM Problem - E - Codeforces
Throw a ball at the box located at coordinate 2. The ball travels through
throw
3 coordinates 2 → 3 → 4 → 6 and stops at coordinate 6, so the response is
2
3. Note that the response is different because of the swap.
Throw a ball at the box located at coordinate 1. The ball travels through
throw
3 coordinates 1 → 3 → 4 → 6 and stops at coordinate 6, so the response is
1
3.
! 2 1
The solution concludes that the power values are [2, 1, 2, 1] .
2 1
There are 2 boxes in the second test case. The hidden power values are
2
a = [1, 2] .
throw Throw a ball at the box located at coordinate 1. The ball travels through
2
1 coordinates 1 → 2 → 4 and stops at coordinate 4, so the response is 2.
Swap the boxes located at coordinate 1 and 2. Now box 1 is located at
swap 1
coordinate 2 and box 2 is located at coordinate 1.
throw Throw a ball at the box located at coordinate 1. The ball travels through
1
1 coordinates 1 → 3 and stops at coordinate 3, so the response is 1.
! 1 2 The solution concludes that the power values are [1, 2].
Empty lines in the example input and output are given only for better readability; you don't need
to output them in your solution.
Note that in the first test case, the given queries are in fact insufficient to uniquely determine the
power values; they are given only to illustrate the input/output format.
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/13/2025 04:11:08UTC+5.5 (k2).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
https://codeforces.com/contest/2134/problem/E 3/3
