Submission #1237349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237349		voidheart	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	65 ms	1888 KiB

subsequence

/*
 
               .;;;;:
              :::::::;
              ;::::::;
               :;;;;.
                 ;:::;
                 ;:::::;;                                                           ;;;
                ::::::::::;;                                                       ;:::
                ;:::::::::::;;:                                                  .;;:::
               .;::::::::::::::;;.                  .:.::::                   ;;;:::;;;
               :;:::::::::::::::::;;.            :. .::::....:            :;;::::::::;
               ;::::::::::....:::::::;;;;;;;;;;: .:...  ....:..:      .;;::::::::::::;
              :;::::::::........::::::::::::::. :. .. ...  .  .....;;;:::::::::::::::;
              ;::::::::..........::::::::::::: ....   .....   .....:::::::::::::::::;:
             .;:::::::...........::::::::::::  :.. ...    ...........:::::::::::::::;.
            ......................::::::::::: ..   ....    ..............:::::::::::;
            ..........:::.......:::::::::::::. . ..    ....    ............:::::::::;
            ..........::::::::::::::::.......: .:....    ...    ........ .:  ::::::;;
              ........:::::::::::::...........:. ::. ....   ....    ....   .: .::::;:
              .......:::::::::::::..............::. .::..     ..    ....    .:..:::;:
               ...::::::::::::::::..:::....::....::::.   :....   ....   ....  : ::.
               ;::::::::::::::::::..::.....:::...::::::::. .:.    ...   ..... .. .
              :;::::::::;;   .;:::::............:::::::::::  :....    ... ..  :.:
              ;:::::::;.        ;;:::.......:::::;;;;..;;;::. :....   ....   ...:
              ;:::::;:            .;;::::::;;;;.           ;;:...   ..  .. .:. .
              ;::::::                :;;:                   .;:: ....... .:. :
              ;::::;     ;.                                   ;;::  :::.. .:;:
              ;;::;:    :;;;;;;                               .;::::::::::::;
               ;::;:    .;;;;;;;                               :;::::::::::::
               .;:;:    .::;;;;;                               .;::::::::::;.
                .;;;.....;;;;;;       ...                      .;:::::::::;.
                  ;;:....             .:.          ;;;;;;      :;::::::::;.
                   :;:.........                        .....   ;:::::::;:
                    .............       ..             ...... :;:::::;:
                ................... .;;;.  .:;.              ;;:::;;:
               ..  .......        ..:;;:;;      ;:         :;::;;:
               ;.:::..   ..........:;;;;;        .;...:.;;;;;.               .
               :;:;.................;.;:;         ;:::::::::             ;;;:::
                  .;....:........;; ;;:::;        .:::::;;:::;.:::.   .;:::::::
                  .:...:; ;..:.:.:::.:;;;:::.       :;:: :   ..:.:.     .;:::::
                  ::.........;;+:....:; .:..::        .::..;           ;::;:;;:
                  ;:...........::;;;;;:  .:: .;      ::..:. :.       ;:::;.  :.
                  ::::::...;.        ::::      ..;;;.        ;.   ;;:::;.
                  .. ::.;:.;:     .::;;;                      ;;;:::;;.
                ::.;   :;;;;:::........;                      ;:::;:
               .;...::::........;:.....:;                     ;:
*/
 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define endl '\n'
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define rev(i,a,b) for(int i=a; i>=b; --i)
#define getbit(mask,i) (1ll&(mask>>i))
#define all(v) (v).begin(),(v).end()
#define isz(v) (int)(v).size()
#define pii pair<int,int>
using namespace std;
const ll inf = 1e9+7;
const ll pvhmod =  1e9 [phone];
const ll moreinf = 1e14 + 7;
const ll base = 256;
const int sz = 300;

const ll MOD[] = {(1ll<<31)-1, (ll)1e9 + 33};
 
inline ll CELL(ll a, ll b){return a/b + (a%b>0);}
inline ll FLOOR(ll a, ll b){return a/b - (a%b<0);}
 
const int maxN = 1e5+7;

int n,a[maxN],b[maxN];

namespace sub1{
    bool check(){
        return n<=20;
    }
    vector<int> v;
    bool x[maxN];
    void ghin(){
        vector<int> tmp;
        rep(i,1,n) if(x[i]) tmp.push_back(i);
        bool ok = 1;
        rep(i,1,isz(tmp)-1){
            // cout << tmp[i] << " ";
            if(__builtin_popcount(a[tmp[i-1]] & a[tmp[i]])!=b[tmp[i]]) ok = 0;
        }
        // cout << endl;
        if(ok && isz(tmp) > isz(v)) v = tmp;
    }
    void backtrack(int i){
        rep(j,0,1){
            x[i] = j;
            if(i==n) ghin();
            else backtrack(i+1);
        }
    }
    void solve(){
        backtrack(1);
        cout << isz(v) << endl;
        for(int x:v) cout << x << " ";
    }
}

namespace sub2{
    bool check(){
        return n<=5000;
    }
    int dp[5005], trace[5005];

    void solve(){
        rep(i,1,n) dp[i] = 1;
        rep(i,2,n){
            rep(j,1,i-1){
                if(__builtin_popcount(a[i] & a[j])==b[i]){
                    if(dp[i] < 1 + dp[j]){
                        dp[i] = 1 + dp[j];
                        trace[i] = j;
                    }
                }
            }
        }
        int mx = 0, sta = 0;
        rep(i,1,n){
            if(mx < dp[i]){
                mx = dp[i];
                sta = i;
            }
        }
        vector<int> ans;
        while(sta > 0){
            ans.push_back(sta);
            sta = trace[sta];
        }
        cout << mx << endl;
        reverse(all(ans));
        for(int x:ans) cout << x << " ";
    }
}

namespace sub3{
    bool check(){
        rep(i,1,n) if(a[i] > (1<<8)) return 0;
        return 1;
    }
    int dp[maxN], trace[maxN];
    pii mx[1<<8];

    void solve(){
        rep(i,1,n) dp[i] = 1;
        mx[a[1]] = {1,1};
        rep(i,2,n){
            rep(x,0,(1<<8)-1){
                int j = mx[x].second, _dp = mx[x].first;
                if(__builtin_popcount(a[i] & x) == b[i]){
                    if(dp[i] < 1 + _dp){
                        dp[i] = 1 + _dp;
                        trace[i] = j;
                    }

                }
            }
            if(mx[a[i]].first < dp[i]){
                mx[a[i]] = {dp[i],i};
            }
        }
        int mx = 0, sta = 0;
        rep(i,1,n){
            if(mx < dp[i]){
                mx = dp[i];
                sta = i;
            }
        }
        vector<int> ans;
        while(sta > 0){
            ans.push_back(sta);
            sta = trace[sta];
        }
        cout << mx << endl;
        reverse(all(ans));
        for(int x:ans) cout << x << " ";
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
    if(fopen("code.inp","r")){
        freopen("code.inp","r",stdin);
        freopen("code.out","w",stdout);
    }
    if(fopen("evenpath.inp","r")){
        freopen("evenpath.inp","r",stdin);
        freopen("evenpath.out","w",stdout);
    }

    cin >> n;
    rep(i,1,n) cin >> a[i];    
    rep(i,1,n) cin >> b[i];
    // cout << 1 << endl;

    // if(sub1::check()) return sub1::solve(),0;
    if(sub2::check()) return sub2::solve(),0;
    if(sub3::check()) return sub3::solve(),0;

    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen("code.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen("code.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:194:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |         freopen("evenpath.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         freopen("evenpath.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60