結果
問題 |
No.1460 Max of Min
|
ユーザー |
![]() |
提出日時 | 2021-04-01 00:02:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 2,855 bytes |
コンパイル時間 | 1,216 ms |
コンパイル使用メモリ | 112,124 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-15 23:12:06 |
合計ジャッジ時間 | 10,662 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 91 |
コンパイルメッセージ
main.cpp: In function 'void sol::solve()': main.cpp:99:28: warning: narrowing conversion of 'v1.std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'LL' {aka 'long long int'} [-Wnarrowing] 99 | LL z[3]={-1,v1.size()}; | ~~~~~~~^~
ソースコード
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<deque> #include<iomanip> #include<tuple> #include<cassert> #include<set> #include<complex> #include<numeric> #include<functional> #include<unordered_map> #include<unordered_set> #include<bitset> using namespace std; typedef long long int LL; typedef pair<int,int> P; typedef pair<LL,LL> LP; const int INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(LL *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } namespace sol{ const LL N=1111; bitset<N> A,B; bitset<N*N*2> C; LL n,m; bool check(){ LL i,j,k; LL a,b,c; LL mod=-1; C.reset(); if(m<n)return A[m]; for(i=0;i<n;i++){ if(B[i])mod=n-i; C[i]=A[i]; } if(mod==-1)return false; for(i=0;i<n;i++){ for(j=0;j<n;j++){ C[n+i]=C[n+i]|(C[i+j]&B[j]); } } vector<char> used(mod); for(i=n;i<N*N;i+=mod){ for(j=0;j<mod;j++){ if(used[j] || !C[i+j])continue; for(k=1;k<=n;k++){ if(B[n-k])C[i+j+k]=1; } used[j]=1; } for(j=0;j<mod;j++){ C[i+mod+j]=C[i+mod+j]|C[i+j]; } } if(m<N*N)return C[m]; LL pos=m-(m-i)/mod*mod; return C[pos]; } void solve(){ LL i,j,k; LL a,b,c; cin>>n>>m; vector<LL> v1,va,vb; for(i=0;i<n;i++){ cin>>a; va.push_back(a); v1.push_back(a); } for(i=0;i<n;i++){ cin>>a; vb.push_back(a); v1.push_back(a); } sort(v1.begin(),v1.end()); LL z[3]={-1,v1.size()}; while(z[1]-z[0]>1){ z[2]=(z[0]+z[1])/2; a=v1[z[2]]; A.reset(),B.reset(); for(i=0;i<n;i++){ if(va[i]>=a)A.set(i,1); if(vb[i]>=a)B.set(i,1); } if(check())z[0]=z[2]; else z[1]=z[2]; } cout<<v1[z[0]]<<endl; } } int main(){ sol::solve(); }