Submission #1237306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237306		voidheart	Longest beautiful sequence (IZhO17_subsequence)	C++20	7 / 100	5 ms	328 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 << " ";
    }
}

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;

    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:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("code.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("code.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("evenpath.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("evenpath.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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