#752131 (C++23) No.5005 3-SAT

提出ソース

結果

問題	No.5005 3-SAT
ユーザー	butsurizuki
提出日時	2022-04-07 02:33:12
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,992 ms / 2,000 ms
コード長	2,059 bytes
コンパイル時間	4,735 ms
実行使用メモリ	3,736 KB
スコア	89,153
最終ジャッジ日時	2022-04-29 13:55:00
合計ジャッジ時間	210,968 ms
ジャッジサーバーID （参考情報）	judge12 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,992 ms 3,612 KB
testcase_01	AC	1,991 ms 3,696 KB
testcase_02	AC	1,991 ms 3,648 KB
testcase_03	AC	1,991 ms 3,544 KB
testcase_04	AC	1,991 ms 3,676 KB
testcase_05	AC	1,992 ms 3,696 KB
testcase_06	AC	1,992 ms 3,692 KB
testcase_07	AC	1,991 ms 3,612 KB
testcase_08	AC	1,992 ms 3,672 KB
testcase_09	AC	1,991 ms 3,692 KB
testcase_10	AC	1,992 ms 3,688 KB
testcase_11	AC	1,992 ms 3,732 KB
testcase_12	AC	1,991 ms 3,544 KB
testcase_13	AC	1,991 ms 3,700 KB
testcase_14	AC	1,991 ms 3,636 KB
testcase_15	AC	1,991 ms 3,704 KB
testcase_16	AC	1,992 ms 3,736 KB
testcase_17	AC	1,992 ms 3,728 KB
testcase_18	AC	1,991 ms 3,640 KB
testcase_19	AC	1,992 ms 3,688 KB
testcase_20	AC	1,992 ms 3,544 KB
testcase_21	AC	1,991 ms 3,696 KB
testcase_22	AC	1,992 ms 3,612 KB
testcase_23	AC	1,992 ms 3,676 KB
testcase_24	AC	1,991 ms 3,676 KB
testcase_25	AC	1,992 ms 3,612 KB
testcase_26	AC	1,992 ms 3,724 KB
testcase_27	AC	1,990 ms 3,636 KB
testcase_28	AC	1,992 ms 3,728 KB
testcase_29	AC	1,992 ms 3,540 KB
testcase_30	AC	1,991 ms 3,684 KB
testcase_31	AC	1,991 ms 3,668 KB
testcase_32	AC	1,991 ms 3,544 KB
testcase_33	AC	1,991 ms 3,644 KB
testcase_34	AC	1,992 ms 3,668 KB
testcase_35	AC	1,991 ms 3,540 KB
testcase_36	AC	1,992 ms 3,720 KB
testcase_37	AC	1,992 ms 3,704 KB
testcase_38	AC	1,992 ms 3,652 KB
testcase_39	AC	1,991 ms 3,632 KB
testcase_40	AC	1,991 ms 3,548 KB
testcase_41	AC	1,991 ms 3,688 KB
testcase_42	AC	1,992 ms 3,636 KB
testcase_43	AC	1,992 ms 3,548 KB
testcase_44	AC	1,992 ms 3,552 KB
testcase_45	AC	1,991 ms 3,676 KB
testcase_46	AC	1,992 ms 3,596 KB
testcase_47	AC	1,992 ms 3,680 KB
testcase_48	AC	1,991 ms 3,640 KB
testcase_49	AC	1,992 ms 3,732 KB
testcase_50	AC	1,991 ms 3,704 KB
testcase_51	AC	1,991 ms 3,540 KB
testcase_52	AC	1,991 ms 3,540 KB
testcase_53	AC	1,992 ms 3,648 KB
testcase_54	AC	1,992 ms 3,544 KB
testcase_55	AC	1,992 ms 3,636 KB
testcase_56	AC	1,992 ms 3,612 KB
testcase_57	AC	1,991 ms 3,608 KB
testcase_58	AC	1,990 ms 3,548 KB
testcase_59	AC	1,992 ms 3,680 KB
testcase_60	AC	1,992 ms 3,716 KB
testcase_61	AC	1,992 ms 3,588 KB
testcase_62	AC	1,992 ms 3,684 KB
testcase_63	AC	1,991 ms 3,688 KB
testcase_64	AC	1,992 ms 3,648 KB
testcase_65	AC	1,992 ms 3,700 KB
testcase_66	AC	1,991 ms 3,688 KB
testcase_67	AC	1,992 ms 3,728 KB
testcase_68	AC	1,992 ms 3,720 KB
testcase_69	AC	1,991 ms 3,536 KB
testcase_70	AC	1,992 ms 3,592 KB
testcase_71	AC	1,992 ms 3,644 KB
testcase_72	AC	1,992 ms 3,664 KB
testcase_73	AC	1,992 ms 3,664 KB
testcase_74	AC	1,992 ms 3,544 KB
testcase_75	AC	1,991 ms 3,664 KB
testcase_76	AC	1,992 ms 3,696 KB
testcase_77	AC	1,992 ms 3,728 KB
testcase_78	AC	1,992 ms 3,544 KB
testcase_79	AC	1,992 ms 3,596 KB
testcase_80	AC	1,991 ms 3,732 KB
testcase_81	AC	1,990 ms 3,692 KB
testcase_82	AC	1,992 ms 3,640 KB
testcase_83	AC	1,992 ms 3,612 KB
testcase_84	AC	1,992 ms 3,652 KB
testcase_85	AC	1,992 ms 3,684 KB
testcase_86	AC	1,991 ms 3,648 KB
testcase_87	AC	1,991 ms 3,632 KB
testcase_88	AC	1,991 ms 3,592 KB
testcase_89	AC	1,991 ms 3,592 KB
testcase_90	AC	1,992 ms 3,544 KB
testcase_91	AC	1,991 ms 3,544 KB
testcase_92	AC	1,992 ms 3,668 KB
testcase_93	AC	1,990 ms 3,684 KB
testcase_94	AC	1,992 ms 3,676 KB
testcase_95	AC	1,992 ms 3,684 KB
testcase_96	AC	1,991 ms 3,676 KB
testcase_97	AC	1,991 ms 3,716 KB
testcase_98	AC	1,992 ms 3,716 KB
testcase_99	AC	1,991 ms 3,644 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<sys/time.h>
#define B_SIZE 256
#define C_SIZE 2048

using namespace std;

long long start_time;

void start_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  start_time=(tv.tv_sec*1000000+tv.tv_usec);
}

long long current_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  return (current_time-start_time);
  //cout << current_time-start_time << "(us)\n";
}

uint32_t xor64(void){
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 13); x = x ^ (x >> 7);
  return x = x ^ (x << 17);
}

int a[C_SIZE][3];
char p[C_SIZE][3];
int mxm=-1;
string res,cs;
set<int> unsat;
int sat_cnt[C_SIZE]={0};

using pi=pair<int,int>;
vector<vector<pi>> g;

int main(){
  start_clock();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  g.resize(B_SIZE);
  for(int i=0;i<C_SIZE;i++){
    cin >> a[i][0] >> a[i][1] >> a[i][2];
    int pp,qq,rr;
    cin >> pp >> qq >> rr;
    p[i][0]=(pp+'0');
    p[i][1]=(qq+'0');
    p[i][2]=(rr+'0');

    g[a[i][0]].push_back({i,0});
    g[a[i][1]].push_back({i,1});
    g[a[i][2]].push_back({i,2});

    if(pp==0){sat_cnt[i]++;}
    if(qq==0){sat_cnt[i]++;}
    if(rr==0){sat_cnt[i]++;}
    if(sat_cnt[i]==0){unsat.insert(i);}
  }
  for(int i=0;i<B_SIZE;i++){cs.push_back('0');}

  int i=0;
  while(1){
    int od=(*unsat.begin());
    if(mxm<od){
      mxm=od;
      res=cs;
    }
    int fp=a[od][xor64()%3];
    for(auto &ny : g[fp]){
      if(cs[fp]==p[ny.first][ny.second]){
        sat_cnt[ny.first]--;
        if(sat_cnt[ny.first]==0){unsat.insert(ny.first);}
      }
      else{
        if(sat_cnt[ny.first]==0){unsat.erase(ny.first);}
        sat_cnt[ny.first]++;
      }
    }
    cs[fp]=('0'+'1'-cs[fp]);
    //cerr << fp << '\n';
    i++;
    if(i==100){
      if(current_clock()>=1990000){break;}
      i=0;
    }
  }
  //cout << mxm << '\n';
  reverse(res.begin(),res.end());
  cout << res << '\n';
  return 0;
}

yukicoder

結果

テストケース

ソースコード