結果
| 問題 | No.1508 Avoid being hit |
| コンテスト | |
| ユーザー |
 southsidesamurai65-prog
|
| 提出日時 | 2026-08-18 15:33:54 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 100 ms / 3,000 ms |
| + 878µs | |
| コード長 | 3,332 bytes |
| 記録 | |
| コンパイル時間 | 1,671 ms |
| コンパイル使用メモリ | 216,264 KB |
| 実行使用メモリ | 17,580 KB |
| 最終ジャッジ日時 | 2026-08-18 15:34:02 |
| 合計ジャッジ時間 | 6,440 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 43 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/char_traits.h:59,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/ios:44,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/ostream.h:43,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/ostream:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/iostream:43,
from main.cpp:1:
In function 'constexpr _Tp* std::construct_at(_Tp*, _Args&& ...) [with _Tp = int; _Args = {const int&}]',
inlined from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/alloc_traits.h:716:21,
inlined from 'void std::deque<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_deque.h:1609:30,
inlined from 'void std::stack<_Tp, _Sequence>::push(const value_type&) [with _Tp = int; _Sequence = std::deque<int, std::allocator<int> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_stack.h:287:20,
inlined from 'int main()' at main.cpp:102:21:
/home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_construct.h:110:16: warning: 'rst' may be used uninitialized [-Wmaybe-uninitialized]
110 | return ::new(__loc) _Tp(std::forward<_Args>(__args)...);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:92:13: note: 'rst' was declared here
92 | int rst;
| ^~~
ソースコード
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
//一回合只敲2个格子，只有在两边才可能被击中
//正常在中间走就不会出事，除非有连击逼到边上
//dp，一开始所有格都是1，1会往两边蔓延，只有被hit变成0，只有hit两端才可能有意义，1一定在中间连着，双指针维护两侧的端点优化dp
int main(){
int n,q;
cin>>n>>q;
vector<int> a(q+1);
vector<int> b(q+1);
for(int i=1;i<=q;i++){
cin>>a[i];
}
for(int i=1;i<=q;i++){
cin>>b[i];
}
vector<map<int,int>> vm(q+1); //用于回溯
int h=1;int t=n;
for(int r=1;r<=q-1;r++){
//cout<<"round "<<r<<": "<<h<<" "<<t<<endl;
set<int> id;
id.insert(a[r]);id.insert(b[r]);
if(t==h){
if(id.count(t)==1){
cout<<"NO"<<endl;
return 0;
}
}else if(t==h+1){ //长度2
if(id.count(h)==1&&id.count(t)==1){
cout<<"NO"<<endl;
return 0;
}else if(id.count(h)==1&&id.count(t)==0){
vm[r+1][h]=t;
if(t+1<=n){
vm[r+1][t+1]=t;
t++;
}
}else if(id.count(h)==0&&id.count(t)==1){
vm[r+1][t]=h;
if(h-1>0){
vm[r+1][h-1]=h;
h--;
}
}else{
if(h-1>0){
vm[r+1][h-1]=h;
h--;
}
if(t+1<=n){
vm[r+1][t+1]=t;
t++;
}
}
}else{ //>=3
if(id.count(h)==1&&id.count(h+1)==1){
vm[r+1][h+1]=h+2;
h++;
}else if(id.count(h)==0&&h-1>0){
vm[r+1][h-1]=h;
h--;
}else if(id.count(h)==1){
vm[r+1][h]=h+1;
}
if(id.count(t)==1&&id.count(t-1)==1){
vm[r+1][t-1]=t-2;
t--;
}else if(id.count(t)==0&&t+1<=n){
vm[r+1][t+1]=t;
t++;
}else if(id.count(t)==1){
vm[r+1][t]=t-1;
}
if(t<h){
cout<<"NO"<<endl;
return 0;
}
}
//两端延伸都更新了
if(h<a[r]&&a[r]<t) vm[r+1][a[r]]=(a[r]-1==b[r]?a[r]+1:a[r]-1);
if(h<b[r]&&b[r]<t) vm[r+1][b[r]]=(b[r]-1==a[r]?b[r]+1:b[r]-1);
}
if(h==t&&(a[q]==h||b[q]==h)){
cout<<"NO"<<endl;
}else if(t==h+1&&min(a[q],b[q])==h&&max(a[q],b[q])==t){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
int rst;
for(int i=h;i<=t;i++){
if(a[q]!=i&&b[q]!=i){
rst=i;
break;
}
}
stack<int> pos;
int r=q;
while(r>=1){
pos.push(rst);
if(vm[r].find(rst)==vm[r].end()){
r--;
}else{
rst=vm[r][rst];
r--;
}
}
cout<<pos.top()<<endl;;
while(!pos.empty()){
cout<<pos.top()<<endl;
pos.pop();
}
}
return 0;
}