結果

問題 No.1804 Intersection of LIS
ユーザー smiken_61
提出日時 2022-02-13 21:37:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 9,448 bytes
コンパイル時間 1,410 ms
コンパイル使用メモリ 174,452 KB
実行使用メモリ 27,068 KB
最終ジャッジ日時 2024-06-29 05:48:09
合計ジャッジ時間 5,049 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::vector<long long int> LIS_strict_fukugen(std::vector<long long int>)’:
main.cpp:380:46: warning: ‘ima’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  380 |                 if(W[i]==nx && (nx==lis_size || ima<A[i])){
      |                                ~~~~~~~~~~~~~~^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

    #include <bits/stdc++.h>
 //   #include <atcoder/all>
     
     
     
     
  //  using namespace atcoder;
     
     
    // tabaicho see https://boostjp.github.io/tips/multiprec-int.html   
    // #include <boost/multiprecision/cpp_int.hpp>
     
    // using namespace boost::multiprecision;
     
    // cpp_int
    // int128_t
    // int256_t
    // int512_t
    // int1024_t
     
    // uint128_t
    // uint256_t
    // uint512_t
    // uint1024_t
     
     
    #define int long long
     #define inf  1000000007
    // #define inf  998244353
     
     #define pa pair<int,int>
     #define ppa pair<pa,pa>
     #define ll long long
     #define PI 3.14159265358979323846
     #define  mp make_pair
     #define  pb push_back
     #define EPS (1e-8)
     
          using namespace std;
                                              
     int dx[8]={0,1,0,-1,1,1,-1,-1};
     int dy[8]={1,0,-1,0,-1,1,1,-1};
                                                
    class pa3{
        public:
        int x;
        int y,z;
        pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
        bool operator < (const pa3 &p) const{
            if(x!=p.x) return x<p.x;
            if(y!=p.y) return y<p.y;
             return z<p.z;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator > (const pa3 &p) const{
            if(x!=p.x) return x>p.x;
            if(y!=p.y) return y>p.y;
             return z>p.z;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa3 &p) const{
            return x==p.x && y==p.y && z==p.z;
        }
            bool operator != (const pa3 &p) const{
                return !( x==p.x && y==p.y && z==p.z);
        }
     
    };
     
    class pa4{
        public:
        int x;
        int y,z,w;
        pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
        bool operator < (const pa4 &p) const{
            if(x!=p.x) return x<p.x;
            if(y!=p.y) return y<p.y;
            if(z!=p.z)return z<p.z;
            return w<p.w;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator > (const pa4 &p) const{
            if(x!=p.x) return x>p.x;
            if(y!=p.y) return y>p.y;
            if(z!=p.z)return z>p.z;
            return w>p.w;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa4 &p) const{
            return x==p.x && y==p.y && z==p.z &&w==p.w;
        }
            
     
    };
    class pa2{
        public:
        int x,y;
        pa2(int x=0,int y=0):x(x),y(y) {}
        pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
        pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
        bool operator < (const pa2 &p) const{
            return y != p.y ? y<p.y: x<p.x;
        }
        bool operator > (const pa2 &p) const{
            return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa2 &p) const{
            return abs(x-p.x)==0 && abs(y-p.y)==0;
        }
        bool operator != (const pa2 &p) const{
            return !(abs(x-p.x)==0 && abs(y-p.y)==0);
        }
            
     
    };
     
     
     
    string itos( int i ) {
        ostringstream s ;
        s << i ;
        return s.str() ;
    }
     
    int Gcd(int v,int b){
        if(v==0) return b;
        if(b==0) return v;
        if(v>b) return Gcd(b,v);
        if(v==b) return b;
        if(b%v==0) return v;
        return Gcd(v,b%v);
    }
     
     
     
    int extgcd(int a, int b, int &x, int &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        int d = extgcd(b, a%b, y, x);
        y -= a/b * x;
        return d;
    }
    pa operator+(const pa & l,const pa & r) {   
        return {l.first+r.first,l.second+r.second};                                    
    }    
    pa operator-(const pa & l,const pa & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
     
    pair<double,double> operator-(const pair<double,double> & l,const pair<double,double> & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
    ostream& operator<<(ostream& os, const vector<int>& VEC){
        for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     ostream& operator<<(ostream& os, const pair<double,double>& PAI){
        os<<PAI.first<<" : "<<PAI.second;
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const pa& PAI){
        os<<PAI.first<<" : "<<PAI.second;
        return os;
    }
     
    ostream& operator<<(ostream& os, const pa3& PAI){
        os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z;
        return os;
    }
     
    ostream& operator<<(ostream& os, const pa4& PAI){
        os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.w;
        return os;
    }
     
    ostream& operator<<(ostream& os, const vector<pa>& VEC){
        for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const vector<pa3>& VEC){
        for(auto v:VEC){
            os<<v<<" ";
        os<<endl;
        }
        return os;
    }
     
    int beki(int wa,ll rr,int warukazu){
        if(rr==0) return 1%warukazu;
        if(rr==1) return wa%warukazu;
        wa%=warukazu;
        if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
        ll zx=beki(wa,rr/2,warukazu);
        return (zx*zx)%warukazu;
    }
     
     
                  
    int pr[2500002];
    int inv[2500002];
     
     
     
     
   const int mod=998244353;
    int comb(int nn,int rr){
        if(nn==-1&&rr==-1)return 1;
        if(rr<0 || rr>nn || nn<0) return 0;
        int r=pr[nn]*inv[rr];
        r%=mod;
        r*=inv[nn-rr];
        r%=mod;
        return r;
    }
     
    void gya(int ert){
        pr[0]=1;
        for(int i=1;i<=ert;i++){
            pr[i]=((ll)pr[i-1]*i)%mod;
        }
            inv[ert]=beki(pr[ert],mod-2,mod);
        for(int i=ert-1;i>=0;i--){
            inv[i]=(ll)inv[i+1]*(i+1)%mod;
        }
    }
     
     
    int beki(int a,int b){
        int ANS=1;
        int be=a%mod;
        while(b){
            if(b&1){
                ANS*=be;
                ANS%=mod;
            }
            be*=be;
            be%=mod;
            b/=2;
        }
        return ANS;
    }
     
                    
     
     
                    
                  //   cin.tie(0);
                //  ios::sync_with_stdio(false);
                    //priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                     //sort(ve.begin(),ve.end(),greater<int>());
    //    mt19937(clock_per_sec);
      //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
     // a,b,c : positive int   a*b<=c  <=>  a<=c/b
    //  auto dfs=[&](auto &&self,int r,int p)->int{
    //  };
    class Point{
        public:
        double x,y;
        Point(double x=0,double y=0):x(x),y(y) {}
        Point operator + (Point p) {return Point(x+p.x,y+p.y);}
        Point operator - (Point p) {return Point(x-p.x,y-p.y);}
        Point operator * (double a) {return Point(x*a,y*a);}
        Point operator / (double a) {return Point(x/a,y/a);}
        double absv() {return sqrt(norm());}
        double norm() {return x*x+y*y;}
        bool operator < (const Point &p) const{
            return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const Point &p) const{
            return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
        }
    };
     
    class Line{
        public:
        // y=ax+b
        double a;
        double b;
        Line(double a=0,double b=0):a(a),b(b) {}
        
        double eval(double x){return a*x+b;}
        bool operator < (const Line &p) const{
            return abs(a-p.a)>EPS ? a<p.a: b<p.b;
        }
        
    };
     
    Point intersect_line(Line A,Line B){
        double x=(B.b-A.b)/(A.a-B.a);
        return Point(x,A.eval(x));
    }
     
    Line line_from_2_Point(Point A,Point B){
        // line which through A,B
        double a=(B.y-A.y)/(B.x-A.x);
        return Line(a,A.y-a*A.x);
    }
     
struct unionfind{
    private:
    public:
    
vector<int> par,ranks,kosuu;
    
    void shoki(int N){
        par.resize(N+1,0);
        ranks.resize(N+1,0);
        kosuu.resize(N+1,1);
        for(int i=0;i<=N;i++){
            par[i]=i;
        }
    }
    int root(int x){
        return par[x]==x ? x : par[x]=root(par[x]);
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    bool is_root(int x){
        return x==root(x);
    }
    void unite(int x,int y){
        x=root(x);
        y=root(y);
        int xx=kosuu[x],yy=kosuu[y];
        if(x==y) return;
        if(ranks[x]<ranks[y]){
            par[x]=y;
            kosuu[y]=yy+xx;
        }
        else {
            par[y]=x;
            if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
            kosuu[x]=yy+xx;
        }
        return;
    }
};
vector<int> LIS_strict_fukugen(vector<int>A){
    int n=A.size();
    vector<int>B=A;
    reverse(B.begin(),B.end());
    for(auto &v:B)v*=-1;
    vector<int>t;
    int sz=0;
    vector<int>W(n); //W_i is max lis size of [A_i,...,A_{n-1}]
    
    
    int lis_size=-1;
    for(int i=0;i<n;i++){
        int v=B[i];
        int r=lower_bound(t.begin(),t.end(),v)-t.begin();
        if(r>=sz)t.pb(0),sz++;
        t[r]=v;
        W[n-1-i]=r+1;
        lis_size=max(lis_size,r+1);
    }
    vector<int>ans;
    int nx=lis_size;
    int ima;
    for(int i=0;i<n;i++){
        if(W[i]==nx && (nx==lis_size || ima<A[i])){
            ans.pb(i);
            ima=A[i];
            nx--;
        }
    }
    return ans;
}
void solve(){
    int n;
    cin>>n;
    vector<int>A(n),B;
    for(int i=0;i<n;i++)cin>>A[i];
    B=A;
    reverse(B.begin(),B.end());
    for(auto &v:B)v*=-1;
    
    auto S= LIS_strict_fukugen(A);
    auto T= LIS_strict_fukugen(B);
    
    for(auto &v:T)v=n-1-v;
    reverse(T.begin(),T.end());
    //cout<<S<<endl<<T<<endl;
    vector<int>ans;
    int s=T.size();
    for(int i=0;i<s;i++){
        if(S[i]==T[i])ans.pb(A[S[i]]);
    }
    cout<<ans.size()<<endl;
    cout<<ans<<endl;
    
}
  
    
    signed main(){
     
        //mod=inf;
        cin.tie(0);
        ios::sync_with_stdio(false);
        int n=1;
        //cin>>n;
        for(int i=0;i<n;i++)solve();
     
        return 0;
        
    }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0