結果

問題 No.1508 Avoid being hit
ユーザー noya2noya2
提出日時 2021-04-04 01:18:01
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 199 ms / 3,000 ms
コード長 8,408 bytes
コンパイル時間 4,956 ms
コンパイル使用メモリ 270,544 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-04-10 05:31:44
合計ジャッジ時間 10,548 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 175 ms
8,576 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 51 ms
7,424 KB
testcase_17 AC 30 ms
6,944 KB
testcase_18 AC 28 ms
6,940 KB
testcase_19 AC 43 ms
6,944 KB
testcase_20 AC 70 ms
8,960 KB
testcase_21 AC 47 ms
7,040 KB
testcase_22 AC 60 ms
7,808 KB
testcase_23 AC 64 ms
8,576 KB
testcase_24 AC 197 ms
10,496 KB
testcase_25 AC 180 ms
9,984 KB
testcase_26 AC 14 ms
6,940 KB
testcase_27 AC 91 ms
6,940 KB
testcase_28 AC 93 ms
6,940 KB
testcase_29 AC 183 ms
9,984 KB
testcase_30 AC 96 ms
6,944 KB
testcase_31 AC 159 ms
9,216 KB
testcase_32 AC 175 ms
9,472 KB
testcase_33 AC 48 ms
6,944 KB
testcase_34 AC 163 ms
9,088 KB
testcase_35 AC 17 ms
6,940 KB
testcase_36 AC 91 ms
6,940 KB
testcase_37 AC 41 ms
6,944 KB
testcase_38 AC 130 ms
8,064 KB
testcase_39 AC 83 ms
6,940 KB
testcase_40 AC 167 ms
9,216 KB
testcase_41 AC 96 ms
6,940 KB
testcase_42 AC 169 ms
9,344 KB
testcase_43 AC 199 ms
10,368 KB
testcase_44 AC 2 ms
6,940 KB
testcase_45 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
/*
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using bint = mp::cpp_int;
*/
#include <atcoder/all>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using namespace atcoder;
using namespace internal;
//alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library'
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PI = pair<pair<int,int>,int>;
using PL = pair<long long, long long>;
using PLL = pair<pair<long long, long long>, long long>;
using Pxy = pair<long double, long double>;
const int INF = 1001001007;
const int modd = 1000000007;
const long long modl = 1000000007LL;
const long long mod = 998244353LL;
const ll inf = 2e18;

template <typename SA>
void priv(vector<SA> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename SB>
void privv(vector<vector<SB>> &ar){
    rep(i,ar.size()){
        rep(j,ar[i].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[i].size()-1] << endl;
    }
}
template <typename SC>
bool range(SC a, SC b, SC x){return (a <= x && x < b);}
bool rrange(P a, P b, P xy){
    bool s = range(a.first,b.first,xy.first);
    bool t = range(a.second,b.second,xy.second);
    return (s && t);
}
template <typename SD>
void sor(vector<SD> &ar){sort(ar.begin(),ar.end());}
template <typename SE>
void rev(vector<SE> &ar){reverse(ar.begin(),ar.end());}
template <typename SF>
bool chmin(SF &a, const SF &b){if(a>b){a = b; return true;} return false;}
template <typename SG>
bool chmax(SG &a, const SG &b){if(a<b){a = b; return true;} return false;}
template <typename SH>
void eru(vector<SH> &ar){sor(ar);ar.erase(unique(ar.begin(),ar.end()),ar.end());}
template <typename SI>
SI   last(vector<SI> &ar){return ar[ar.size()-1];}
template <typename SJ>
SJ   cel(SJ a, SJ b){if (a % b == 0) return a/b; return a/b +1;}
template <typename SK, typename SL>
void pout(pair<SK,SL> p) {cout << p.first << " " << p.second << endl;}

void yes(){cout << "Yes" << endl;}
void no (){cout << "No" << endl;}
void yn (bool t){if(t)yes();else no();}
void Yes(){cout << "YES" << endl;}
void No (){cout << "NO" << endl;}
void YN (bool t){if(t)Yes();else No();}
void dout() {cout << setprecision(20);}

vector<int> dx = {0,1,0,-1};
vector<int> dy = {1,0,-1,0};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

void inc(vector<P> &a, int n){
    int m = a.size();
    rep(i,m){
        a[i].first = max(1,a[i].first - 1);
        a[i].second = min(n,a[i].second + 1);
    }
}
//a C b
bool crossin(P a, P b){
    return (b.first <= a.first && a.second <= b.second);
}

P crossand(P a, P b){
    if (a.first <= b.second && b.first <= a.second){
        return P(max(a.first,b.first),min(a.second,b.second));
    }
    else return P(-1,-1);
}

vector<P> uni(int n, vector<P> a, int x, int y){
    if (a.size() == 0) return a;
    inc(a,n);
    vector<int> ap;
    rep(i,a.size()){
        ap.emplace_back(a[i].first);
        ap.emplace_back(a[i].second);
    }
    eru(ap);
    vector<P> ans;
    int nowle = ap[0];
    int nowri = ap[0];
    int w = ap.size();
    rep(i,w-1){
        int ile = ap[i];
        int iri = ap[i+1];
        bool t = false;
        rep(j,a.size()) if (crossin(P(ile,iri),a[j])) t = true;
        if (t) nowri = iri;
        else {
            ans.emplace_back(P(nowle,nowri));
            nowle = iri;
            nowri = iri;
        }
    }
    if (nowri - nowle > 0) ans.emplace_back(P(nowle,nowri));
    int m = ans.size();
    vector<P> rec;
    if (x == y){
        rep(i,m){
            if (ans[i].first == x || ans[i].second == x){
                if (ans[i].first == x) ans[i].first = x+1;
                else if (ans[i].second == x) ans[i].second = x-1;
                rec.emplace_back(ans[i]);
            } 
            else if (ans[i].first <= x && x <= ans[i].second) {
                rec.emplace_back(P(ans[i].first,x-1));
                rec.emplace_back(P(x+1,ans[i].second));
            }
            else rec.emplace_back(ans[i]);
        }
    }
    else if (x + 1 == y){
        rep(i,m){
            if (ans[i].first == x && ans[i].second == y) continue;
            if (ans[i].first <= x && y <= ans[i].second){
                if (ans[i].first == x || ans[i].second == y){
                    if (ans[i].first == x) ans[i].first = y+1;
                    else if (ans[i].second == y) ans[i].second = x-1;
                    rec.emplace_back(ans[i]);
                }
                else {
                    rec.emplace_back(P(ans[i].first,x-1));
                    rec.emplace_back(P(y+1,ans[i].second));
                }
            }
            else if (ans[i].first == y){
                rec.emplace_back(P(y+1,ans[i].second));
            }
            else if (ans[i].second == x){
                rec.emplace_back(P(ans[i].first,x-1));
            }
            else rec.emplace_back(ans[i]);
        }
    }
    else {
        rep(i,m){
            if (ans[i].first <= x && y <= ans[i].second){
                if (ans[i].first == x && ans[i].second == y){
                    rec.emplace_back(P(x+1,y-1));
                }
                else if (ans[i].first == x || ans[i].second == y){
                    if (ans[i].first == x){
                        rec.emplace_back(P(x+1,y-1));
                        rec.emplace_back(P(y+1,ans[i].second));
                    }
                    else if (ans[i].second == y){
                        rec.emplace_back(P(ans[i].first,x-1));
                        rec.emplace_back(P(x+1,y-1));
                    }
                }
                else {
                    rec.emplace_back(P(ans[i].first,x-1));
                    rec.emplace_back(P(x+1,y-1));
                    rec.emplace_back(P(y+1,ans[i].second));
                }
            }
            else if (ans[i].first <= x && x <= ans[i].second){
                if (ans[i].first == x){
                    rec.emplace_back(P(x+1,ans[i].second));
                }
                else if (ans[i].second == x){
                    rec.emplace_back(P(ans[i].first,x-1));
                }
                else {
                    rec.emplace_back(P(ans[i].first,x-1));
                    rec.emplace_back(P(x+1,ans[i].second));
                }
            }
            else if (ans[i].first <= y && y <= ans[i].second){
                if (ans[i].first == y){
                    rec.emplace_back(P(y+1,ans[i].second));
                }
                else if (ans[i].second == y){
                    rec.emplace_back(P(ans[i].first,y-1));
                }
                else {
                    rec.emplace_back(P(ans[i].first,y-1));
                    rec.emplace_back(P(y+1,ans[i].second));
                }
            }
            else rec.emplace_back(ans[i]);
        }
    }
    return rec;
}

bool ok(vector<P> a, int x){
    int n = a.size();
    rep(i,n){
        if (range(a[i].first,a[i].second+1,x)) return true;
    }
    return false;
}

int main(){
    int n, q; cin >> n >> q;
    vector<P> ar(q);
    rep(i,q) cin >> ar[i].first;
    rep(i,q) cin >> ar[i].second;
    rep(i,q) if (ar[i].first > ar[i].second) swap(ar[i].first,ar[i].second);
    vector<P> ini = {P(1,n)};
    vector<vector<P>> rng(q+1,vector<P>(0));
    rng[0] = ini;
    rep(i,q){
        rng[i+1] = uni(n,rng[i],ar[i].first,ar[i].second);
    }
    if (rng[q].size() == 0){
        No();
        return 0;
    }
    Yes();
    vector<int> ans(q+1);
    ans[q] = rng[q][0].first;
    for (int i = q-1; i >= 0; i--){
        int l = ans[i+1] -1;
        int m = ans[i+1];
        int r = ans[i+1] +1;
        if (ok(rng[i],l)) ans[i] = l;
        else if (ok(rng[i],m)) ans[i] = m;
        else ans[i] = r;
    }
    rep(i,q+1) cout << ans[i] << endl; /*
    rep(i,q+1){
        rep(j,rng[i].size()){
            cout << '[' << rng[i][j].first << " " << rng[i][j].second << "] ";
        }
        cout << endl;
    }*/
}
0