QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528365 | #9161. Naval battle | Dimash# | 6 | 2341ms | 216132kb | C++17 | 3.9kb | 2024-08-23 13:16:19 | 2024-08-23 13:16:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 12, MOD = (int)1e9 + 7;
int n;
map<int,set<array<int,3>>> v[4],h[4],d[4],db[4];
int conv(char dir) {
if(dir == 'N') {
return 0;
} else if(dir == 'E') {
return 1;
} else if(dir == 'S') {
return 2;
}
return 3;
}
void add(int x,int y,int dir,int i) {
if(dir == 1 || dir == 3) {
h[dir][y].insert({x,y,i});
} else {
v[dir][x].insert({x,y,i});
}
d[dir][x + y].insert({x,y,i});
db[dir][x - y].insert({x,y,i});
}
int cur[N];
set<pair<int,int>> st;
void del(int x,int y,int dir,int i) {
st.erase({cur[i],i});
if(dir == 1 || dir == 3) {
h[dir][y].erase({x,y,i});
} else {
v[dir][x].erase({x,y,i});
}
d[dir][x + y].erase({x,y,i});
db[dir][x - y].erase({x,y,i});
}
int x[N],y[N],dir[N];
const int inf = (int)1e9 + 2;
const int dx[] = {0,1,0,-1},dy[] = {-1,0,1,0};
int dist(int i,int j) {
if(i == j || j == -1) return inf;
int ret = abs(x[i] - x[j]) / 2 + abs(y[i] - y[j]) / 2;
int x1 = x[i] + dx[dir[i]] * ret,y1 = y[i] + dy[dir[i]] * ret;
int x2 = x[j] + dx[dir[j]] * ret,y2 = y[j] + dy[dir[j]] * ret;
return (x1 == x2 && y1 == y2 ? ret : inf);
}
int nx(set<array<int,3>> &st,int i){
array<int,3> f = {x[i],y[i],i};
auto it = st.lower_bound(f);
if(it == st.end()) return -1;
return (*it)[2];
}
int prev(set<array<int,3>> &st,int i) {
array<int,3> f = {x[i],y[i],i};
auto it = st.lower_bound(f);
if(it == st.begin()) return -1;
it--;
return (*it)[2];
}
int calc(int i) {
int ret = inf;
for(int k = 0;k < 4;k++) {
if(dir[i] == k) continue;
if(dir[i] % 2 == k % 2) {
if(k % 2 == 1) {
int j = nx(h[k][y[i]],i);
ret = min(ret,dist(i,j));
j = prev(h[k][y[i]],i);
ret = min(ret,dist(i,j));
} else {
int j = nx(v[k][x[i]],i);
ret = min(ret,dist(i,j));
j = prev(v[k][x[i]],i);
ret = min(ret,dist(i,j));
}
} else {
{
int j = nx(d[k][x[i] + y[i]],i);
ret = min(ret,dist(i,j));
j = prev(d[k][x[i] + y[i]],i);
ret = min(ret,dist(i,j));
}
{
int j = nx(db[k][x[i] - y[i]],i);
ret = min(ret,dist(i,j));
j = prev(db[k][x[i] - y[i]],i);
ret = min(ret,dist(i,j));
}
}
}
return ret;
}
map<array<int,3>,int> id;
void test() {
cin >> n;
for(int i = 1;i <= n;i++) {
char di;
cin >> x[i] >> y[i] >> di;
dir[i] = conv(di);
add(x[i],y[i],dir[i],i);
st.insert({0,i});
id[{x[i],y[i],dir[i]}] = i;
}
while(!st.empty()) {
auto [val,v] = (*st.begin());
if(val == inf) {
break;
}
st.erase(st.begin());
int _ = calc(v);
assert(_ >= val);
if(val != _) {
cur[v] = _;
st.insert({_,v});
continue;
}
int x1 = x[v] + dx[dir[v]] * val,y1 = y[v] + dy[dir[v]] * val;
for(int i = 0;i < 4;i++) {
int X = x1 + dx[i],Y = y1 +dy[i];
int d;
if(i % 2 == 0) {
d = 2 - i;
} else {
d = 4 - i;
}
if(id.count({X,Y,d})) {
del(X,Y,d,id[{X,Y,d}]);
}
}
}
for(auto [x,y]:st) {
cout << y << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 1ms
memory: 5636kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 5620kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3664kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 1ms
memory: 5580kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 1ms
memory: 5680kb
input:
2 509095668 374922996 W 325521434 191348762 S
output:
result:
ok
Test #6:
score: 6
Accepted
time: 1ms
memory: 5580kb
input:
2 357656592 713571312 E 456601638 614626266 S
output:
result:
ok
Test #7:
score: 6
Accepted
time: 1ms
memory: 5624kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 1ms
memory: 5772kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 1ms
memory: 5676kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 1ms
memory: 5740kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 1ms
memory: 5768kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 0ms
memory: 3636kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 1ms
memory: 5608kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 12
Accepted
time: 1ms
memory: 5768kb
input:
100 32 46 N 8 24 W 74 86 W 2 76 N 90 70 N 34 74 N 4 68 N 42 26 N 66 94 N 28 40 W 96 12 W 82 78 W 54 24 N 36 42 W 92 68 W 0 26 N 14 54 N 94 66 N 26 52 N 66 12 W 72 6 W 64 96 W 6 20 N 4 22 W 26 42 N 40 28 W 70 76 N 18 60 N 62 16 N 30 48 N 36 36 W 42 36 W 52 94 N 62 98 N 0 78 N 70 2 W 28 50 N 80 80 W 8...
output:
result:
ok
Test #15:
score: 12
Accepted
time: 1ms
memory: 5836kb
input:
100 70 62 N 56 42 N 42 56 W 64 4 N 50 48 W 56 76 N 78 20 W 96 96 W 60 72 N 44 24 N 2 10 N 52 80 W 38 30 N 94 4 W 58 74 W 68 30 W 54 76 N 0 68 N 36 32 N 10 58 W 70 60 W 86 92 N 100 78 W 2 66 W 20 48 N 16 52 N 8 60 N 98 94 N 86 46 W 74 24 W 26 42 W 66 66 W 28 40 W 56 12 W 90 42 W 8 4 W 76 30 W 78 54 W...
output:
result:
ok
Test #16:
score: 0
Wrong Answer
time: 1ms
memory: 3684kb
input:
100 36 44 E 96 66 E 28 20 E 36 2 E 32 64 W 76 58 E 82 20 E 76 50 E 22 48 W 38 52 E 90 16 N 22 12 W 64 82 S 84 14 E 92 52 E 76 36 E 72 52 N 100 58 S 82 4 E 2 0 N 90 100 E 68 8 S 24 36 S 80 86 W 72 56 W 8 66 W 84 18 S 18 60 N 64 96 E 2 76 S 74 90 E 64 0 S 12 10 S 56 40 S 40 6 S 2 4 S 74 2 S 90 80 N 2 ...
output:
1 2 3 4 5 6 8 10 11 12 13 14 15 19 20 21 23 24 26 28 29 30 31 32 33 35 36 37 39 40 41 42 45 46 47 49 50 51 53 54 56 57 58 59 61 62 63 64 65 69 70 71 73 74 76 77 78 79 81 83 84 85 87 89 91 92 93 95 96 98 99
result:
wrong answer
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 30
Accepted
time: 2259ms
memory: 159880kb
input:
200000 526715640 430855204 E 731546662 226024182 S 254814720 702756124 E 227354364 730216480 S 764250602 193320242 S 150102088 807468756 E 204858572 752712272 S 635512190 322058654 E 403910248 553660596 S 257917918 4587926 S 949444340 8126504 S 907805098 49765746 S 553836306 403734538 S 40977864 617...
output:
result:
ok
Test #59:
score: 30
Accepted
time: 2146ms
memory: 159952kb
input:
200000 49807058 551453536 S 912071804 329648260 E 419320288 181940306 S 782015644 459704420 E 481787934 119472660 S 415682572 185578022 E 179604736 421655858 E 301356118 299904476 E 353873612 271679996 E 228215568 373045026 S 135196366 466064228 E 283328822 317931772 S 46447784 554812810 S 316201696...
output:
result:
ok
Test #60:
score: 30
Accepted
time: 2341ms
memory: 174468kb
input:
176146 300873980 786927014 E 790003068 165796398 E 749865014 863323264 S 436936218 157236050 S 397770254 450222406 S 485732108 78259410 S 41354530 472465106 E 887439666 371255344 E 124841048 192531136 S 148591896 22935244 S 306340430 586720996 E 567973664 846954348 S 684406062 154686710 E 693649864 ...
output:
result:
ok
Test #61:
score: 30
Accepted
time: 2316ms
memory: 174272kb
input:
176200 925233074 814682098 E 568432234 13441354 S 484262992 272477328 S 158978078 20120660 S 893397554 160241062 S 751909180 715444298 S 208992058 827145154 S 412237740 546261136 S 338408780 271805998 E 815418640 355051290 E 976553702 905622826 E 857611462 834179634 S 906111624 426633546 S 403730260...
output:
result:
ok
Test #62:
score: 30
Accepted
time: 1705ms
memory: 216124kb
input:
200000 101496054 979858228 E 920611908 702401460 S 520518410 139919454 E 399656414 901493922 E 13516644 96042148 E 245648844 231035904 E 764355194 276588538 S 996306054 310601486 E 786798600 855338184 E 994867310 672987224 S 579872970 756137766 S 781862354 643502988 S 84441740 245739906 S 203009366 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #63:
score: 30
Accepted
time: 1682ms
memory: 216052kb
input:
200000 527978012 655552976 E 367561552 287545914 E 109269874 785653618 S 593357740 388019526 S 559862448 71088562 S 757736766 642977878 E 596651936 802122060 E 726526424 755843838 E 907457664 73340276 E 115634476 26185946 S 373222698 792179306 E 326091516 103452644 E 409098972 861128728 E 486159912 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #64:
score: 30
Accepted
time: 1731ms
memory: 216132kb
input:
200000 840116210 558689674 E 419874916 668247716 E 706701702 531127374 S 1235386 416545400 E 729427828 202817966 E 343924344 473507730 S 56565780 233269258 E 662681036 328877994 E 179823328 572544632 E 785195282 51398910 S 854800144 214285546 E 379414682 1601316 S 901409854 730921418 E 801144786 716...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #65:
score: 0
Wrong Answer
time: 1697ms
memory: 67136kb
input:
200000 300 1080 E 168 1186 S 244 968 S 218 1566 S 400 736 E 244 364 S 112 1722 E 144 1164 E 178 470 S 242 1626 E 2 456 E 278 760 E 242 1442 E 196 302 S 188 314 S 414 512 E 50 1162 S 114 1056 E 314 412 E 398 1302 S 408 1658 S 288 1490 E 184 134 E 348 544 E 234 1760 E 196 1472 S 280 376 E 324 1662 S 4...
output:
83 109 163 182 307 500 550 602 662 757 878 893 930 1127 1138 1164 1186 1432 1504 1655 1705 1727 1736 1756 1922 1997 2114 2156 2184 2216 2293 2432 2434 2489 2639 3003 3175 3182 3375 3514 3544 3613 3660 3765 3863 3880 4071 4102 4221 4250 4440 4711 4819 4897 5002 5219 5271 5412 5428 5468 5482 5512 5550...
result:
wrong answer
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%