QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #504455 | #9161. Naval battle | kwongweng# | 30 | 55ms | 5856kb | C++17 | 2.8kb | 2024-08-04 13:14:02 | 2024-08-04 13:14:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second
ll MOD = 998244353;
ll power(ll base, ll n){
base %= MOD;
if (n==0) return 1;
ll halfn = power(base,n/2);
if (n%2==0) return (halfn*halfn)%MOD;
return (((halfn*halfn)%MOD)*base)%MOD;
}
ll inverse(ll n){
return power(n,MOD-2);
}
ll C[3001][3001];
ll binom(int n, int k){
if (C[n][k]!=-1) return C[n][k];
if (n<k) return C[n][k] = 0;
if (k==0) return C[n][k] = 1;
return C[n][k] = (binom(n-1,k)+binom(n-1,k-1)) % MOD;
}
vll mul(vll A, vll B){
int n = A.size();
int m = B[0].size();
int p = B.size();
vll C; C.resize(n, vector<ll>(m,0LL));
FOR(i,0,n){
FOR(j,0,m){
FOR(k,0,p){
C[i][j] += (A[i][k]*B[k][j]) % MOD;
C[i][j] %= MOD;
}
}
}
return C;
}
vll exp(vll base, ll n){
int len = base.size();
vll ans; ans.resize(len,vector<ll>(len,0LL));
FOR(i,0,len) ans[i][i]=1;
if (n==0) return ans;
if (n==1) return base;
ans = mul(exp(base,n/2),exp(base,n/2));
if (n % 2 == 1) ans = mul(ans,base);
return ans;
}
/*
bipartite -> Alice wins
*/
const int N = 2001;
vi p(N), sz(N);
set<int> par;
int get(int a){
if (p[a]==a) return a;
return p[a]=get(p[a]);
}
void Union(int a, int b){
int c = get(a), d = get(b);
if (sz[c]<sz[d]) swap(c,d);
sz[c]+=sz[d];
p[d]=c; par.erase(d);
}
ll INF = 1e9;
ll f(ll n){
return ((n*(n+1))/2) % MOD;
}
void solve(){
int n; cin>>n;
vector<pair<ii,int>> ship(n);
vector<char> dir(n+1);
FOR(i,0,n){
int x,y; cin>>x>>y>>dir[i+1];
ship[i] = {{x+y,x},i+1};
}
sort(ship.begin(), ship.end());
int cur = 0;
while (cur<n){
int nxt = n;
FOR(j,cur+1,n){
if (ship[j].fi.fi != ship[cur].fi.fi){
nxt = j; break;
}
}
stack<int> st;
FOR(j,cur,nxt){
if (dir[ship[j].se] == 'E'){
st.push(ship[j].se);
}else{
if (st.empty()) cout<<ship[j].se<<"\n";
else st.pop();
}
}
while (!st.empty()){
cout<<st.top()<<"\n"; st.pop();
}
cur = nxt;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int TC = 1; //cin>>TC;
while (TC--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 3648kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3560kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
2 1
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3640kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
2 1
result:
ok
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3608kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
2 1
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/4.ans)
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3612kb
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:
16 24 23 80 72 2 17 66 25 10 67 26 8 69 7 41 58 47 40 83 54 31 79 77 51 36 35 4 89 42 88 70 93 55 94 28 74 76 62 19 37 30 1 97 14 65 95 32 43 50 85 75 13 82 49 68 29 99 20 46 92 21 45 78 6 84 48 98 71 11 33 44 90 27 59 87 39 61 91 56 52 81 60 64 34 22 9 100 53 3 63 73 38 12 96 57 5 15 18 86
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/14.ans)
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 30
Accepted
Test #58:
score: 30
Accepted
time: 44ms
memory: 5744kb
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: 40ms
memory: 5728kb
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: 33ms
memory: 5556kb
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: 33ms
memory: 5416kb
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: 55ms
memory: 5660kb
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:
54502 126073 114773 152922 126473 193778 30212 188980 85555 122469 19134 138055 46155 167877 28034 113334 157588 98908 154806 180091 199056 76090 182612 122910 5989 166726 60707 160848 153027 28629 139427 81911 52170 190912 104107 8806 189913 116436 140621 199683 104549 35775 79249 132437 135304 194...
result:
ok
Test #63:
score: 30
Accepted
time: 44ms
memory: 5760kb
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:
89277 99460 32625 48000 18150 24960 183975 54077 69806 67083 6835 171695 128981 8779 149460 196103 166841 5949 172063 104170 186153 121687 33873 187537 181824 29500 55086 101091 153425 189109 133444 133514 197496 126461 147884 175148 109289 2783 81387 158702 44644 49768 63653 127444 185441 174093 16...
result:
ok
Test #64:
score: 30
Accepted
time: 55ms
memory: 5760kb
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:
30911 188742 145281 49321 103953 21445 86465 135552 75163 119816 86756 159234 184597 152928 85862 80189 131584 81174 72786 130618 107756 149527 173946 103212 184079 16584 5561 59200 105333 34641 84268 88188 152908 42405 123846 187700 12429 129410 137201 89532 167089 17036 106476 24955 105245 86698 1...
result:
ok
Test #65:
score: 30
Accepted
time: 35ms
memory: 5704kb
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:
184528 114434 88864 63677 165836 188815 165670 22983 187515 51006 180087 114303 195952 87419 94615 109654 139503 11126 179001 122387 44873 157112 75113 7265 137650 168955 163309 15280 89370 115209 91699 106871 91976 19155 187725 60153 6145 64330 64332 183017 14265 10309 165856 155619 194500 8191 934...
result:
ok
Test #66:
score: 30
Accepted
time: 39ms
memory: 5720kb
input:
200000 246 1304 E 372 564 E 282 1226 E 166 302 E 350 256 E 336 860 S 392 1148 E 330 1588 E 446 642 S 86 120 E 276 420 S 418 776 E 90 1420 E 272 400 S 326 470 S 104 232 S 102 284 E 292 708 E 368 1156 E 236 1756 E 412 666 E 6 1756 S 408 332 S 390 466 S 380 480 S 358 374 E 38 818 S 362 482 E 170 630 E ...
output:
176549 43556 131740 177449 195168 15863 137270 130016 193141 151223 110999 53082 156402 132481 184932 33492 189847 42801 60686 60089 174228 158297 165266 74452 89457 124801 177826 120311 15517 8800 161887 180308 134778 22549 106813 76279 176828 186396 26847 199518 194193 49168 78608 49118 39891 1391...
result:
ok
Test #67:
score: 30
Accepted
time: 38ms
memory: 5688kb
input:
200000 36 1570 E 280 458 S 414 498 E 98 336 S 86 794 E 330 362 E 40 964 S 346 386 E 28 604 S 48 1694 S 84 460 S 240 1754 E 340 36 E 206 1332 E 132 612 S 98 426 S 26 172 S 100 960 E 360 610 E 236 546 S 446 42 S 160 1744 E 166 258 S 144 978 S 170 1626 S 416 18 S 252 1356 S 258 1278 E 352 1028 S 442 12...
output:
177580 96513 166975 122124 76173 62683 70904 139090 190878 5420 112272 36350 1520 51324 178955 9929 100331 160977 181337 5442 153722 14371 59323 7424 130418 158631 114185 47383 76946 80481 10131 198969 189453 37236 144219 197714 139358 155434 24605 74687 182744 56290 68930 107558 20663 32653 149573 ...
result:
ok
Test #68:
score: 30
Accepted
time: 38ms
memory: 5676kb
input:
200000 88 1742 E 164 776 E 10 1262 S 200 1200 S 284 716 S 328 1096 E 398 438 S 138 1382 E 296 706 E 422 1780 S 212 228 S 72 1418 S 284 220 E 422 1444 E 314 736 S 140 1370 S 348 188 E 22 720 S 348 1418 S 332 546 S 426 248 E 222 188 S 28 244 S 6 1210 E 144 1358 E 186 54 E 412 638 E 240 1598 E 336 1710...
output:
14607 22635 77269 143322 181029 134005 37990 42655 199209 22137 76646 166494 102872 31435 74569 21385 179265 139886 135283 111399 76583 50822 81728 57747 92441 172548 64038 193635 48329 192294 43 130432 146327 35931 150871 92380 70682 155127 85445 7561 127669 12108 137283 16495 185586 25227 199806 1...
result:
ok
Test #69:
score: 30
Accepted
time: 38ms
memory: 5856kb
input:
200000 100 1404 E 82 1670 S 128 972 E 424 18 E 202 472 E 180 1230 E 320 1606 S 242 1212 E 26 834 E 350 912 S 436 1458 E 18 1476 S 322 1668 E 8 1426 E 0 1644 E 370 1122 S 110 432 E 126 1128 E 338 94 S 344 1736 E 440 516 S 314 1246 E 194 1068 E 358 1386 E 32 1752 E 244 1608 S 292 1494 E 236 1454 S 216...
output:
130719 101810 62088 2249 31471 199665 153256 194566 134664 81129 123116 73040 114098 11618 57413 198969 159960 26687 16113 154335 173901 174575 122495 93088 42910 167003 153915 98771 73985 168445 48208 195856 32951 158555 90794 164255 131274 94072 22259 108655 8874 24163 96150 93182 2989 158760 8382...
result:
ok
Subtask #7:
score: 0
Skipped
Dependency #1:
0%