結果
問題 | No.1508 Avoid being hit |
ユーザー | どらら |
提出日時 | 2021-05-16 08:05:21 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 223 ms / 3,000 ms |
コード長 | 2,931 bytes |
コンパイル時間 | 4,093 ms |
コンパイル使用メモリ | 232,204 KB |
実行使用メモリ | 25,240 KB |
最終ジャッジ日時 | 2024-04-15 01:41:08 |
合計ジャッジ時間 | 9,841 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 167 ms
13,988 KB |
testcase_01 | AC | 5 ms
8,132 KB |
testcase_02 | AC | 4 ms
8,112 KB |
testcase_03 | AC | 5 ms
8,240 KB |
testcase_04 | AC | 4 ms
8,324 KB |
testcase_05 | AC | 4 ms
8,416 KB |
testcase_06 | AC | 5 ms
8,332 KB |
testcase_07 | AC | 3 ms
8,264 KB |
testcase_08 | AC | 3 ms
8,348 KB |
testcase_09 | AC | 4 ms
8,172 KB |
testcase_10 | AC | 4 ms
8,340 KB |
testcase_11 | AC | 4 ms
8,176 KB |
testcase_12 | AC | 5 ms
8,428 KB |
testcase_13 | AC | 4 ms
8,128 KB |
testcase_14 | AC | 3 ms
8,216 KB |
testcase_15 | AC | 4 ms
8,236 KB |
testcase_16 | AC | 61 ms
13,868 KB |
testcase_17 | AC | 37 ms
11,552 KB |
testcase_18 | AC | 34 ms
10,568 KB |
testcase_19 | AC | 52 ms
13,000 KB |
testcase_20 | AC | 80 ms
14,792 KB |
testcase_21 | AC | 54 ms
12,580 KB |
testcase_22 | AC | 66 ms
13,684 KB |
testcase_23 | AC | 73 ms
14,068 KB |
testcase_24 | AC | 212 ms
23,492 KB |
testcase_25 | AC | 198 ms
22,244 KB |
testcase_26 | AC | 17 ms
9,256 KB |
testcase_27 | AC | 100 ms
15,104 KB |
testcase_28 | AC | 100 ms
15,184 KB |
testcase_29 | AC | 198 ms
22,508 KB |
testcase_30 | AC | 109 ms
15,812 KB |
testcase_31 | AC | 175 ms
20,676 KB |
testcase_32 | AC | 192 ms
21,684 KB |
testcase_33 | AC | 54 ms
11,840 KB |
testcase_34 | AC | 181 ms
22,040 KB |
testcase_35 | AC | 22 ms
9,496 KB |
testcase_36 | AC | 103 ms
15,948 KB |
testcase_37 | AC | 47 ms
11,540 KB |
testcase_38 | AC | 145 ms
19,140 KB |
testcase_39 | AC | 94 ms
15,252 KB |
testcase_40 | AC | 188 ms
22,800 KB |
testcase_41 | AC | 109 ms
16,312 KB |
testcase_42 | AC | 191 ms
23,008 KB |
testcase_43 | AC | 223 ms
25,240 KB |
testcase_44 | AC | 5 ms
8,392 KB |
testcase_45 | AC | 3 ms
8,316 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; //using mint = modint1000000007; //using mint = modint998244353; class Range { public: struct RNG { ll l, r; bool operator<(const RNG& a) const { return r < a.r; } }; set<RNG> rngs; void add(ll nl, ll nr){ RNG rng; rng.l = nl; rng.r = nr; auto bgn = rngs.lower_bound((RNG){nl-1,nl-1}); auto it = bgn; for(; it != rngs.end(); it++){ if(it->l <= rng.r+1){ nl = min(nl, it->l); nr = max(nr, it->r); }else{ break; } } rngs.erase(bgn, it); rngs.insert((RNG){nl,nr}); } void erase(ll nl, ll nr){ RNG rng; rng.l = nl; rng.r = nr; set<RNG> tmp; auto bgn = rngs.lower_bound((RNG){nl,nl}); auto it = bgn; for(; it != rngs.end(); it++){ if(it->l <= rng.r){ if(it->l < nl){ tmp.insert((RNG){it->l,nl-1}); } if(nr < it->r){ tmp.insert((RNG){nr+1,it->r}); } }else{ break; } } rngs.erase(bgn, it); FOR(it,tmp){ rngs.insert(*it); } } }; Range ok[100005]; vector<int> solve(int N, const vector<pair<int,int>>& v){ int Q = v.size(); vector<int> ret; { int a = v[Q-1].first; int b = v[Q-1].second; ok[Q-1].add(1,N); ok[Q-1].erase(a,a); ok[Q-1].erase(b,b); } for(int i=Q-2; i>=0; i--){ int a = v[i].first; int b = v[i].second; if(a > b) swap(a,b); FOR(it,ok[i+1].rngs){ int aa = it->l - 1; int bb = it->r + 1; aa = max(aa, 1); bb = min(bb, N); ok[i].add(aa,bb); } ok[i].erase(a,a); ok[i].erase(b,b); } /* rep(i,Q){ cout << i << endl; FOR(it,ok[i]){ cout << "\t" << it->first << " " << it->second << endl; } } */ if(ok[0].rngs.size() == 0) return vector<int>(); int pos = ok[0].rngs.begin()->l; ret.push_back(pos); REP(i,1,Q){ int nxt = pos; REP(j,-1,2){ int npos = pos + j; bool flg = false; if(1<=npos&&npos<=N){ FOR(it,ok[i].rngs){ if(it->l <= npos && npos <= it->r) flg = true; } } if(flg){ nxt = npos; break; } } pos = nxt; ret.push_back(pos); } return ret; } int main(){ int N, Q; cin >> N >> Q; vector<pair<int,int>> v(Q); rep(i,Q) cin >> v[i].first; rep(i,Q) cin >> v[i].second; vector<int> ret = solve(N, v); if(ret.size() > 0){ cout << "YES" << endl; cout << ret[0] << endl; rep(i,ret.size()) cout << ret[i] << endl; return 0; } cout << "NO" << endl; return 0; }