結果

問題 No.5005 3-SAT
ユーザー rhoo
提出日時 2022-07-07 19:40:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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