Solutions are presented as using the least memory and the fastest execution time. It also takes the top
10 most recent solutions from each language. If you want to limit to a specific index, click the
"Solved" button and go to that problem.
Problems
B"You are working for the Gryzzl company, headquartered in Pawnee, Indiana. The new national park has been opened near Pawnee recently and you are to implement a geolocation system, so people won't get lost. The concept you developed is innovative and minimalistic. There will be n antennas located somewhere in the park. When someone would like to know their current location, their Gryzzl hologram phone will communicate with antennas and obtain distances from a user's current location to all antennas. Knowing those distances and antennas locations it should be easy to recover a user's location... Right? Well, almost. The only issue is that there is no way to distinguish antennas, so you don't know, which distance corresponds to each antenna. Your task is to find a user's location given as little as all antennas location and an unordered multiset of distances. The first line of input contains a single integer n ( 2 <= q n <= q 10^5 ) which is the number of antennas. The following n lines contain coordinates of antennas, i -th line contain two integers x_i and y_i ( 0 <= q x_i,y_i <= q 10^8 ). It is guaranteed that no two antennas coincide. The next line of input contains integer m ( 1 <= q n cdot m <= q 10^5 ), which is the number of queries to determine the location of the user. Following m lines contain n integers 0 <= q d_1 <= q d_2 <= q ... <= q d_n <= q 2 cdot 10^{16} each. These integers form a multiset of squared distances from unknown user's location (x;y) to antennas. For all test cases except the examples it is guaranteed that all user's locations (x;y) were chosen uniformly at random, independently from each other among all possible integer locations having 0 <= q x, y <= q 10^8 . For each query output k , the number of possible a user's locations matching the given input and then output the list of these locations in lexicographic order. It is guarantee"... |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
60976883 |
DjaNik |
G |
Sept. 21, 2019, 7:31 a.m. |
OK |
GNU C++11 |
TESTS |
220 |
873 |
47001600 |
|
3200 |
60840161 |
totoagainto |
G |
Sept. 19, 2019, 10:38 a.m. |
OK |
GNU C++11 |
TESTS |
220 |
873 |
47001600 |
|
3200 |
61612240 |
LittleBeetle |
G |
Oct. 1, 2019, 2:28 p.m. |
OK |
GNU C++11 |
TESTS |
220 |
1107 |
51097600 |
|
3200 |
62523060 |
asc |
G |
Oct. 13, 2019, 4:22 p.m. |
OK |
GNU C++11 |
TESTS |
220 |
1122 |
51302400 |
|
3200 |
60816766 |
MiFaFaOvO |
G |
Sept. 18, 2019, 8:40 p.m. |
OK |
GNU C++14 |
TESTS |
220 |
499 |
47104000 |
|
3200 |
60829623 |
NeverSee |
G |
Sept. 19, 2019, 6:18 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
529 |
47104000 |
|
3200 |
65794999 |
Injetzk |
G |
Nov. 27, 2019, 3:40 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
576 |
4096000 |
|
3200 |
65794949 |
Injetzk |
G |
Nov. 27, 2019, 3:36 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
577 |
4096000 |
|
3200 |
65794937 |
Injetzk |
G |
Nov. 27, 2019, 3:35 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
608 |
4096000 |
|
3200 |
65794914 |
Injetzk |
G |
Nov. 27, 2019, 3:34 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
608 |
4096000 |
|
3200 |
61837587 |
idxcalcal |
G |
Oct. 4, 2019, 8:31 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
624 |
2662400 |
|
3200 |
63274950 |
Toxel |
G |
Oct. 24, 2019, 6:24 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
1013 |
2457600 |
|
3200 |
65794607 |
Injetzk |
G |
Nov. 27, 2019, 3:13 a.m. |
OK |
GNU C++14 |
TESTS |
220 |
1169 |
51302400 |
|
3200 |
62156751 |
arthurpd |
G |
Oct. 8, 2019, 5:05 p.m. |
OK |
GNU C++14 |
TESTS |
220 |
1482 |
3584000 |
|
3200 |
65795021 |
KevinWan |
G |
Nov. 27, 2019, 3:41 a.m. |
OK |
GNU C++17 |
TESTS |
220 |
561 |
4096000 |
|
3200 |
61033064 |
.__. |
G |
Sept. 21, 2019, 6:29 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
686 |
82534400 |
|
3200 |
60954069 |
hamlulkhair |
G |
Sept. 21, 2019, 1:08 a.m. |
OK |
GNU C++17 |
TESTS |
220 |
686 |
82534400 |
|
3200 |
61021911 |
.__. |
G |
Sept. 21, 2019, 2:50 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
717 |
82534400 |
|
3200 |
60952855 |
.__. |
G |
Sept. 20, 2019, 11:33 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
717 |
82534400 |
|
3200 |
61032960 |
.__. |
G |
Sept. 21, 2019, 6:26 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
733 |
82534400 |
|
3200 |
60952767 |
.__. |
G |
Sept. 20, 2019, 11:26 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
733 |
82534400 |
|
3200 |
60845080 |
Benq |
G |
Sept. 19, 2019, 12:17 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
795 |
4096000 |
|
3200 |
60952715 |
.__. |
G |
Sept. 20, 2019, 11:22 p.m. |
OK |
GNU C++17 |
TESTS |
220 |
826 |
82534400 |
|
3200 |
61189046 |
Xellos |
G |
Sept. 24, 2019, 1:27 a.m. |
OK |
GNU C++17 |
TESTS |
220 |
1138 |
3174400 |
|
3200 |
60818529 |
MiFaFaOvO |
G |
Sept. 18, 2019, 9:51 p.m. |
OK |
PyPy 2 |
TESTS |
220 |
1730 |
22528000 |
|
3200 |
61027068 |
iwantbechampion |
G |
Sept. 21, 2019, 4:19 p.m. |
OK |
PyPy 2 |
TESTS |
220 |
1731 |
22425600 |
|
3200 |
60819379 |
tourist_plus_kan |
G |
Sept. 18, 2019, 10:35 p.m. |
OK |
PyPy 2 |
TESTS |
220 |
1731 |
22425600 |
|
3200 |
63530957 |
TombRaider |
G |
Oct. 27, 2019, 6:42 a.m. |
OK |
PyPy 2 |
TESTS |
220 |
1731 |
22630400 |
|
3200 |
61297495 |
RNS_JKS |
G |
Sept. 26, 2019, 2:30 a.m. |
OK |
PyPy 3 |
TESTS |
220 |
1887 |
37990400 |
|
3200 |
remove filters
Back to search problems