結果
問題 | No.1508 Avoid being hit |
ユーザー |
![]() |
提出日時 | 2021-05-14 23:44:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,123 bytes |
コンパイル時間 | 2,559 ms |
コンパイル使用メモリ | 206,916 KB |
最終ジャッジ日時 | 2025-01-21 12:31:48 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 WA * 1 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } struct RandomNumberGenerator{ mt19937 mt; RandomNumberGenerator():mt(chrono::steady_clock::now().time_since_epoch().count()){} // [a,b) int operator()(int a,int b){ uniform_int_distribution<int> d(a,b-1); return d(mt); } }; const int LIM=20; signed main(){ mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); RandomNumberGenerator rand; int N,M;cin>>N>>M; vector<int> A(M),B(M); cin>>A>>B; for(auto &x:A) x--; for(auto &x:B) x--; if(N<=LIM){ vector<vector<int>> dp(M+1,vector<int>(N,0)); vector<vector<int>> pre(M+1,vector<int>(N,0)); rep(i,N) dp[0][i]=1; rep(i,M){ rep(j,N){ if(dp[i][j]){ if(j) dp[i+1][j-1]=1,pre[i+1][j-1]=j; if(j+1<N) dp[i+1][j+1]=1,pre[i+1][j+1]=j; dp[i+1][j]=1,pre[i+1][j]=j; } } dp[i+1][A[i]]=0; dp[i+1][B[i]]=0; } int p=-1; rep(i,N) if(dp[M][i]) p=i; if(p<0){ cout<<"NO"<<endl; return 0; } cout<<"YES"<<"\n"; vector<int> res; for(int i=M;i>=0;i--){ res.push_back(p+1); p=pre[i][p]; } reverse(ALL(res)); for(auto &x:res) cout<<x<<"\n"; return 0; } vector<int> res; vector<int> ope{-1,0,1}; rep(_,200){ int p=rand(0,N); res.push_back(p); bool can=true; for(int i=0;i<M;i++){ bool turn=false; for(auto &t:ope){ int np=p+t; if(0<=np and np<N and A[i]!=np and B[i]!=np){ p=np; res.push_back(np); turn=true; break; } } if(!turn){ can=false; break; } shuffle(ALL(ope),mt); } if(can){ cout<<"YES\n"; for(auto &x:res) cout<<x+1<<"\n"; return 0; } } cout<<"NO"<<"\n"; return 0; }