Quiz

Submit

解法1

そのままに実装する
- 制約が緩いので通る

解法2

操作を逆順にたどる
- この解法で解いた
- 解法1より速い
- 星1.5よりは難しい

Code

int main(){
    // input
    cin >> N >> M;
    A.resize(M);
    
    FOR(i, 0, M){
        cin >> A[i];
    }
    
    ll index = 1;

    // うしろから
    for(int i=M-1; i>=0; i--){
        ll a = A[i];
        if(index==1){
            index = a;
        }
        else{
            if(a<index){
                //
            }
            else if(a>=index){
                index--;
            }
        }
    }

    p(index);
    
    return 0;
}

サンプル4

 1  2  3  4  5  6  7  8  9 10 
6番目を動かした結果
 6  1  2  3  4  5  7  8  9 10 
10番目を動かした結果
10  6  1  2  3  4  5  7  8  9 
4番目を動かした結果
 2 10  6  1  3  4  5  7  8  9 
2番目を動かした結果
10  2  6  1  3  4  5  7  8  9 
7番目を動かした結果
 5 10  2  6  1  3  4  7  8  9 
1番目を動かした結果
 5 10  2  6  1  3  4  7  8  9 
4番目を動かした結果
 6  5 10  2  1  3  4  7  8  9 
3番目を動かした結果
10  6  5  2  1  3  4  7  8  9