結果
問題 | No.689 E869120 and Constructing Array 3 |
ユーザー |
![]() |
提出日時 | 2018-05-19 00:17:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 1,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 942 ms |
コンパイル使用メモリ | 100,232 KB |
最終ジャッジ日時 | 2025-01-05 10:41:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include<algorithm> #include<iostream> #include<random> #include<vector> using namespace std; typedef long long lint; typedef vector<int>vi; typedef pair<int,int>pii; #define rep(i,n)for(int i=0;i<(int)(n);++i) const int N=2100000; int pr[N]; void init(){ for(int i=2;i<N;++i)pr[i]=1; for(int i=2;i*i<N;++i){ if(!pr[i])continue; for(int j=2;j*i<N;++j)pr[i*j]=0; } } int main(){ init(); int k; cin>>k; mt19937 mt(0xe869120); int w=250/2; int trial=0; while(1){ trial++; if(trial%100==0)cerr<<"try " << trial<<endl; vi e(w),o(w); rep(i,w){ do{ e[i]=2*(mt()%10)+2; }while(e[i]%3==1); } rep(i,w){ do{ o[i]=2*(mt()%10)+1; }while(o[i]%3==1); } int sum=0; rep(i,w){ rep(j,i){ sum+=pr[e[i]+o[j]]; sum+=pr[e[j]+o[i]]; } sum+=pr[e[i]+o[i]]; if(sum==k){ //found cout<<2*(i+1)<<endl; rep(j,i+1)cout<<e[j]<<" "; rep(j,i+1)cout<<o[j]<<(j==i?"\n":" "); return 0; } if(sum>k)break; } } }