結果

問題 No.1508 Avoid being hit
ユーザー maine_honzuki
提出日時 2021-05-14 22:49:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,301 bytes
コンパイル時間 2,274 ms
コンパイル使用メモリ 200,300 KB
最終ジャッジ日時 2025-01-21 11:51:27
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 1 MLE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:42:16: warning: ‘book’ may be used uninitialized [-Wmaybe-uninitialized]
   42 |         ans[Q] = book;
main.cpp:35:13: note: ‘book’ was declared here
   35 |         int book;
      |             ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(Q), B(Q);
    for (auto&& a : A) {
        cin >> a;
        a--;
    }
    for (auto&& b : B) {
        cin >> b;
        b--;
    }
    vector<bitset<100000>> maine(Q + 1);
    for (int i = 0; i < N; i++) {
        maine[0][i] = 1;
    }
    for (int i = 0; i < Q; i++) {
        maine[i + 1] = (maine[i] << 1) | (maine[i] >> 1);
        maine[i + 1][N] = 0;
        if (maine[i][0])
            maine[i + 1][0] = 1;
        if (maine[i][N - 1])
            maine[i + 1][N - 1] = 1;
        maine[i + 1][A[i]] = 0;
        maine[i + 1][B[i]] = 0;
    }
    if (maine[Q].count() == 0)
        cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        vector<int> ans(Q + 1);
        int book;
        for (int i = 0; i < N; i++) {
            if (maine[Q][i]) {
                book = i;
                break;
            }
        }
        ans[Q] = book;
        for (int i = Q - 1; i >= 0; i--) {
            if (book > 0 && maine[i][book - 1])
                book--;
            else if (book < N - 1 && maine[i][book + 1])
                book++;
            ans[i] = book;
        }
        for (auto&& a : ans) {
            cout << a + 1 << endl;
        }
    }
}
0