結果

問題 No.5005 3-SAT
ユーザー rhoorhoo
提出日時 2022-07-07 19:40:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,983 ms / 2,000 ms
コード長 4,431 bytes
コンパイル時間 4,247 ms
実行使用メモリ 6,952 KB
スコア 108,329
最終ジャッジ日時 2022-07-07 19:43:48
合計ジャッジ時間 208,315 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,983 ms
3,844 KB
testcase_01 AC 1,981 ms
3,852 KB
testcase_02 AC 1,982 ms
4,164 KB
testcase_03 AC 1,982 ms
3,944 KB
testcase_04 AC 1,983 ms
4,216 KB
testcase_05 AC 1,982 ms
3,836 KB
testcase_06 AC 1,982 ms
3,952 KB
testcase_07 AC 1,983 ms
3,916 KB
testcase_08 AC 1,982 ms
4,044 KB
testcase_09 AC 1,983 ms
4,048 KB
testcase_10 AC 1,983 ms
4,212 KB
testcase_11 AC 1,982 ms
3,908 KB
testcase_12 AC 1,982 ms
3,944 KB
testcase_13 AC 1,983 ms
3,852 KB
testcase_14 AC 1,982 ms
3,996 KB
testcase_15 AC 1,982 ms
3,912 KB
testcase_16 AC 1,981 ms
4,164 KB
testcase_17 AC 1,982 ms
3,832 KB
testcase_18 AC 1,982 ms
3,956 KB
testcase_19 AC 1,982 ms
4,048 KB
testcase_20 AC 1,982 ms
4,216 KB
testcase_21 AC 1,982 ms
4,164 KB
testcase_22 AC 1,981 ms
3,948 KB
testcase_23 AC 1,982 ms
3,904 KB
testcase_24 AC 1,982 ms
4,216 KB
testcase_25 AC 1,982 ms
3,844 KB
testcase_26 AC 1,983 ms
4,056 KB
testcase_27 AC 1,982 ms
3,992 KB
testcase_28 AC 1,982 ms
3,992 KB
testcase_29 AC 1,982 ms
3,940 KB
testcase_30 AC 1,983 ms
3,944 KB
testcase_31 AC 1,983 ms
3,940 KB
testcase_32 AC 1,982 ms
3,920 KB
testcase_33 AC 1,983 ms
3,848 KB
testcase_34 AC 1,982 ms
3,832 KB
testcase_35 AC 1,982 ms
3,992 KB
testcase_36 AC 1,982 ms
3,956 KB
testcase_37 AC 1,982 ms
3,996 KB
testcase_38 AC 1,983 ms
3,996 KB
testcase_39 AC 1,982 ms
3,920 KB
testcase_40 AC 1,982 ms
3,944 KB
testcase_41 AC 1,982 ms
3,832 KB
testcase_42 AC 1,982 ms
3,912 KB
testcase_43 AC 1,983 ms
3,992 KB
testcase_44 AC 1,983 ms
3,856 KB
testcase_45 AC 1,983 ms
4,044 KB
testcase_46 AC 1,982 ms
3,948 KB
testcase_47 AC 1,981 ms
3,916 KB
testcase_48 AC 1,982 ms
3,944 KB
testcase_49 AC 1,982 ms
3,956 KB
testcase_50 AC 1,983 ms
3,848 KB
testcase_51 AC 1,983 ms
4,208 KB
testcase_52 AC 1,981 ms
3,948 KB
testcase_53 AC 1,982 ms
4,216 KB
testcase_54 AC 1,982 ms
3,912 KB
testcase_55 AC 1,982 ms
4,000 KB
testcase_56 AC 1,982 ms
3,920 KB
testcase_57 AC 1,981 ms
3,996 KB
testcase_58 AC 1,981 ms
3,952 KB
testcase_59 AC 1,983 ms
4,048 KB
testcase_60 AC 1,982 ms
4,168 KB
testcase_61 AC 1,982 ms
3,916 KB
testcase_62 AC 1,981 ms
3,952 KB
testcase_63 AC 1,983 ms
4,904 KB
testcase_64 AC 1,982 ms
4,900 KB
testcase_65 AC 1,983 ms
4,900 KB
testcase_66 AC 1,983 ms
4,900 KB
testcase_67 AC 1,981 ms
4,904 KB
testcase_68 AC 1,982 ms
5,160 KB
testcase_69 AC 1,982 ms
4,900 KB
testcase_70 AC 1,982 ms
4,904 KB
testcase_71 AC 1,982 ms
5,156 KB
testcase_72 AC 1,982 ms
4,900 KB
testcase_73 AC 1,983 ms
5,156 KB
testcase_74 AC 1,982 ms
4,900 KB
testcase_75 AC 1,982 ms
4,904 KB
testcase_76 AC 1,982 ms
5,156 KB
testcase_77 AC 1,982 ms
4,904 KB
testcase_78 AC 1,982 ms
4,904 KB
testcase_79 AC 1,983 ms
5,156 KB
testcase_80 AC 1,982 ms
4,900 KB
testcase_81 AC 1,982 ms
5,156 KB
testcase_82 AC 1,982 ms
5,160 KB
testcase_83 AC 1,982 ms
4,904 KB
testcase_84 AC 1,982 ms
4,900 KB
testcase_85 AC 1,982 ms
4,904 KB
testcase_86 AC 1,982 ms
4,900 KB
testcase_87 AC 1,981 ms
4,904 KB
testcase_88 AC 1,982 ms
4,904 KB
testcase_89 AC 1,982 ms
4,900 KB
testcase_90 AC 1,983 ms
4,904 KB
testcase_91 AC 1,983 ms
4,904 KB
testcase_92 AC 1,982 ms
4,904 KB
testcase_93 AC 1,981 ms
4,900 KB
testcase_94 AC 1,982 ms
4,904 KB
testcase_95 AC 1,982 ms
4,904 KB
testcase_96 AC 1,983 ms
4,904 KB
testcase_97 AC 1,983 ms
4,904 KB
testcase_98 AC 1,982 ms
5,156 KB
testcase_99 AC 1,982 ms
6,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

// #define LOCAL

using usize=unsigned long long;
using i64=long long;
using f64=double;
template<typename T> using Vec=vector<T>;

__attribute__((constructor)) void constructor(){cin.tie(nullptr);cin.sync_with_stdio(false);}

namespace rnd{
    static usize S=88172645463325252;
    
    inline usize next(){
        S^=S<<7;
        S^=S>>9;
        return S;
    }
}

inline f64 get_time(){
    static f64 START=-1.;
    timespec ts;
    timespec_get(&ts,TIME_UTC);
    f64 t=f64(ts.tv_sec)+f64(ts.tv_nsec)*1e-9;
    if(START<0){START=t;}
    return t-START;
}

#ifdef LOCAL
#define debug(...) debug_sub(0,#__VA_ARGS__,__VA_ARGS__)
template<typename N,typename T>
void debug_sub(int i,const N& name,const T& a){
    for(;name[i]!=',' && name[i]!='\0';++i) cerr<<name[i];
    cerr<<": "<<a<<endl;
}

template<typename N,typename T1,typename... T2>
void debug_sub(int i,const N& name,const T1& a,const T2& ...b){
    for(;name[i]!=',' && name[i]!='\0';++i) cerr<<name[i];
    cerr<<": "<<a<<", ";
    debug_sub(i+1,name,b...);
}
#else
#define debug(...)
#endif


constexpr usize N=256;
constexpr usize M=2048;


struct In{
    array<array<Vec<usize>,2>,N> edge{};

    inline In(){
        usize id[3];
        usize f[3];
        for(usize i=0;i<M;++i){
            cin>>id[0]>>id[1]>>id[2]>>f[0]>>f[1]>>f[2];
            for(usize j=0;j<3;++j){
                edge[id[j]][f[j]].emplace_back(i);
            }
        }
    }
};


struct Out{
    array<bool,N> out{};
    array<usize,M> cnt{};
    array<array<Vec<usize>,2>,N> edge{};

    inline Out(){
        usize r=!0;
        for(usize i=0;i<N;++i){
            if((i&63)==0){
                r=rnd::next();
            }
            out[i]=(r&1)==0;
            r>>=1;
        }
    }

    inline void re(In& input,usize r){
        cnt.fill(0);
        for(usize i=0;i<N;++i){
            for(usize j=0;j<2;++j){
                edge[i][j].clear();

                for(const auto k:input.edge[i][j]){
                    if(k<r){
                        edge[i][j].emplace_back(k);
                    }
                }
            }

            for(const auto j:edge[i][out[i]]){
                ++cnt[j];
            }
        }
    }

    inline i64 score(){
        i64 ret=0;
        for(const auto i:cnt){
            ret+=(i!=0);
        }
        return ret;
    }

    inline bool change(i64 add,usize idx,i64& score){
        i64 diff=0;
        bool f=out[idx];
        for(const auto i:edge[idx][f]){
            --cnt[i];
            diff-=cnt[i]==0;
        }
        for(const auto i:edge[idx][!f]){
            ++cnt[i];
            diff+=cnt[i]==1;
        }

        if(add<=diff){
            score+=diff;
            out[idx]=!f;

            return true;
        }

        for(const auto i:edge[idx][f]) ++cnt[i];
        for(const auto i:edge[idx][!f]) --cnt[i];
        return false;
    }
};


constexpr f64 TL=1.98;


bool sa(usize r,Out& cur,usize lim){
    i64 score=cur.score();

    usize iter=0;
    usize up=0;
    array<i64,256> th;

    for(;;){
        if((iter&2047)==0){
            if(get_time()>=TL) break;

            f64 p=f64(iter)/f64(lim);
            if(p>=1.) break;

            constexpr f64 T=0.3;
            f64 heat=T*(1.-p);

            usize id=0;
            do{
                usize r=rnd::next();
                th[id]=heat*log(f64(r&4294967295)/4294967296.);
                th[id+1]=heat*log(f64(r>>32)/4294967296.);
                id+=2;
            }while(id<th.size());
        }
        ++iter;

        if(cur.change(th[iter&255],rnd::next()%N,score)){
            if(score==r) break;
            ++up;
        }
    }

    f64 p=f64(up)/f64(iter);
    debug(r,iter,p);
    debug(score);

    assert(score==cur.score());

    return score==r;
}


array<bool,256> solve(In& input){
    Out out;
    array<bool,256> ans=out.out;
    usize best=0;

    usize pos=1000;
    usize iter=0;

    while(get_time()<=TL){
        ++iter;
        out.re(input,pos);

        if(sa(pos,out,2000000)){
            ans=out.out;
            best=pos;
            pos+=4;
        }
        else{
            out.out=ans;
            pos=best+1;
        }
    }

    debug(iter);
    debug(best);

    return ans;
}


int main(){
    In input;
    array<bool,256> ans=solve(input);

    for(i64 i=ans.size()-1;0<=i;--i){
        cout<<ans[i];
    }
    cout<<endl;
}
0