QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #711116 | #9161. Naval battle | jinzikai314 | 6 | 536ms | 144264kb | C++14 | 6.9kb | 2024-11-05 00:34:59 | 2024-11-05 00:35:01 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<queue>
#define DEBUG printf("Debug on Line %d\n", __LINE__)
#define int long long
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
inline int read(){
int n=0, f=1; char ch=getchar();
for(; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
for(; isdigit(ch); ch=getchar()) n=n*10+ch-48;
return n*f;
}
inline char gc(){
char ch=getchar();
while(ch!='N' && ch!='S' && ch!='W' && ch!='E') ch=getchar();
return ch;
}
struct node{
int tim;
int id1, id2;
string tpe;
bool operator<(const node &x)const{
return tim > x.tim;
}
};
int n;
int X[N], Y[N];
char d[N];
unordered_map<int, int> mpx, mpy, mpp, mpm;
int tot1, tot2, tot3, tot4;
set<pii> NS[N], WE[N], NW[N], NE[N], SW[N], SE[N];
// pair(id*(N/W/S), id)
priority_queue<node> q;
bool vis[N];
signed main(){
n = read();
for(int i=1; i<=n; i++){
int x = read(), y = read(); char ch = gc();
X[i] = x, Y[i] = y, d[i] = ch;
if(!mpx[x]) mpx[x] = ++tot1;
if(!mpy[y]) mpy[y] = ++tot2;
if(!mpp[x+y]) mpp[x+y] = ++tot3;
if(!mpm[y-x]) mpm[y-x] = ++tot4;
if(ch == 'N'){
NS[mpx[x]].insert(mkp(y, i));
NW[mpp[x+y]].insert(mkp(x, i));
NE[mpm[y-x]].insert(mkp(x, i));
} else if(ch == 'S'){
NS[mpx[x]].insert(mkp(y, i));
SW[mpm[y-x]].insert(mkp(x, i));
SE[mpp[x+y]].insert(mkp(x, i));
} else if(ch == 'W'){
WE[mpy[y]].insert(mkp(x, i));
NW[mpp[x+y]].insert(mkp(x, i));
SW[mpm[y-x]].insert(mkp(x, i));
} else if(ch == 'E'){
WE[mpy[y]].insert(mkp(x, i));
NE[mpm[y-x]].insert(mkp(x, i));
SE[mpp[x+y]].insert(mkp(x, i));
}
}
for(auto i: mpx){
set<pii> st = NS[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'S' && d[nxtid] == 'N'){
q.push({Y[nxtid]-Y[id], nxtid, id, "NS"});
}
if(it == st.begin()) break;
}
}
for(auto i: mpy){
set<pii> st = WE[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'E' && d[nxtid] == 'W'){
q.push({X[nxtid]-X[id], nxtid, id, "WE"});
}
if(it == st.begin()) break;
}
}
for(auto i: mpp){
set<pii> st = NW[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'N' && d[nxtid] == 'W'){
q.push({X[nxtid]-X[id], id, nxtid, "NW"});
}
if(it == st.begin()) break;
}
}
for(auto i: mpm){
set<pii> st = NE[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'E' && d[nxtid] == 'N'){
q.push({X[nxtid]-X[id], nxtid, id, "NE"});
}
if(it == st.begin()) break;
}
}
for(auto i: mpm){
set<pii> st = SW[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'S' && d[nxtid] == 'W'){
q.push({X[nxtid]-X[id], id, nxtid, "SW"});
}
if(it == st.begin()) break;
}
}
for(auto i: mpp){
set<pii> st = SE[i.second];
if(st.size() <= 1) continue;
auto it = st.end();
for(--it, --it;; --it){
int id = it->se, nxtid = next(it)->se;
if(d[id] == 'E' && d[nxtid] == 'S'){
q.push({X[nxtid]-X[id], nxtid, id, "SE"});
}
if(it == st.begin()) break;
}
}
while(!q.empty()){
set<int> del;
int tim = q.top().tim, x = q.top().id1, y = q.top().id2;
string s = q.top().tpe; q.pop();
// printf("queue - %lld %lld %lld\n", tim, x, y);
del.insert(x), del.insert(y);
while(!q.empty() && q.top().tim == tim){
// printf("queue - %lld %lld %lld\n", q.top().tim, q.top().id1, q.top().id2);
del.insert(q.top().id1), del.insert(q.top().id2);
q.pop();
}
for(auto i: del){
vis[i] = 1;
if(d[i] == 'N'){
auto it = NS[mpx[X[i]]].find({Y[i], i});
if(it != NS[mpx[X[i]]].begin()){
auto pit = prev(it);
if(pit != NS[mpx[X[i]]].begin() && next(it) != NS[mpx[X[i]]].end()){
auto ppit = prev(pit), nit = next(it);
if(d[ppit->se] == 'S' && d[nit->se] == 'N')
q.push({X[nit->se]-X[ppit->se], nit->se, ppit->se, "NS"});
}
NS[mpx[X[i]]].erase(it);
NS[mpx[X[i]]].erase(pit);
}
it = NW[mpp[X[i]+Y[i]]].find({X[i], i});
if(it != prev(NW[mpp[X[i]+Y[i]]].end())){
auto pit = next(it);
if(it != NW[mpp[X[i]+Y[i]]].begin() && next(pit) != NW[mpp[X[i]+Y[i]]].end()){
auto ppit = prev(it), nit = next(pit);
if(d[ppit->se] == 'N' && d[nit->se] == 'W')
q.push({X[nit->se]-X[ppit->se], ppit->se, nit->se, "NW"});
}
NW[mpp[X[i]+Y[i]]].erase(it);
NW[mpp[X[i]+Y[i]]].erase(pit);
}
it = NE[mpm[Y[i]-X[i]]].find({X[i], i});
if(it != NE[mpm[Y[i]-X[i]]].begin()){
auto pit = prev(it);
if(pit != NE[mpm[Y[i]-X[i]]].begin() && next(it) != NE[mpm[Y[i]-X[i]]].end()){
auto ppit = prev(pit), nit = next(it);
if(d[ppit->se] == 'E' && d[nit->se] == 'N')
q.push({X[nit->se]-X[ppit->se], nit->se, ppit->se, "NE"});
}
NE[mpm[Y[i]-X[i]]].erase(it);
NE[mpm[Y[i]-X[i]]].erase(pit);
}
} else if(d[i] == 'S'){
auto it = SW[mpm[Y[i]-X[i]]].find({X[i], i});
if(it != SW[mpm[Y[i]-X[i]]].begin()){
auto pit = prev(it);
if(pit != SW[mpm[Y[i]-X[i]]].begin() && next(it) != SW[mpm[Y[i]-X[i]]].end()){
auto ppit = prev(pit), nit = next(it);
if(d[ppit->se] == 'S' && d[nit->se] == 'W')
q.push({X[nit->se]-X[ppit->se], ppit->se, nit->se, "SW"});
}
SW[mpm[Y[i]-X[i]]].erase(it);
SW[mpm[Y[i]-X[i]]].erase(pit);
}
it = SE[mpp[X[i]+Y[i]]].find({X[i], i});
if(it != SE[mpp[X[i]+Y[i]]].begin()){
auto pit = prev(it);
if(pit != SE[mpp[X[i]+Y[i]]].begin() && next(it) != SE[mpp[X[i]+Y[i]]].end()){
auto ppit = prev(pit), nit = next(it);
if(d[ppit->se] == 'E' && d[nit->se] == 'S')
q.push({X[nit->se]-X[ppit->se], nit->se, ppit->se, "SE"});
}
SE[mpp[X[i]+Y[i]]].erase(it);
SE[mpp[X[i]+Y[i]]].erase(pit);
}
} else if(d[i] == 'W'){
auto it = WE[mpy[Y[i]]].find({X[i], i});
if(it != WE[mpy[Y[i]]].begin()){
auto pit = prev(it);
if(pit != WE[mpy[Y[i]]].begin() && next(it) != WE[mpy[Y[i]]].end()){
auto ppit = prev(pit), nit = next(it);
if(d[ppit->se] == 'E' && d[nit->se] == 'W')
q.push({X[nit->se]-X[ppit->se], nit->se, ppit->se, "WE"});
}
WE[mpy[Y[i]]].erase(it);
WE[mpy[Y[i]]].erase(pit);
}
}
}
}
for(int i=1; i<=n; i++){
if(vis[i]) continue;
printf("%lld\n", i);
}
}
详细
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 8ms
memory: 61888kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 8ms
memory: 62104kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 7ms
memory: 62092kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 3ms
memory: 63004kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 7ms
memory: 63048kb
input:
2 509095668 374922996 W 325521434 191348762 S
output:
result:
ok
Test #6:
score: 6
Accepted
time: 8ms
memory: 62608kb
input:
2 357656592 713571312 E 456601638 614626266 S
output:
result:
ok
Test #7:
score: 6
Accepted
time: 5ms
memory: 62316kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 11ms
memory: 63096kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 7ms
memory: 61836kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 8ms
memory: 62360kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 3ms
memory: 61808kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 7ms
memory: 63412kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 3ms
memory: 62224kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
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:
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
Runtime Error
Test #58:
score: 30
Accepted
time: 536ms
memory: 144264kb
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: 531ms
memory: 139116kb
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: 411ms
memory: 135108kb
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: 410ms
memory: 134236kb
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: 445ms
memory: 136348kb
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: 409ms
memory: 136308kb
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: 385ms
memory: 136616kb
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
Runtime Error
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:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%