제출 #1323284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323284		wangzhiyi33	DEL13 (info1cup18_del13)	C++20	100 / 100	15 ms	3500 KiB

del13

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int maxn=1e5;
int dp[maxn+2][3];
int bc[maxn+2][3];

signed main(){
    int tc;
    cin>>tc;
    while(tc--){
        int n,qu;
        cin>>n>>qu;
        qu++;
        int pos[qu+2];
        pos[0]=0;
        for(int q=1;q<qu;q++){
            cin>>pos[q];
        }
        pos[qu]=n+1; pos[qu+1]=n+2;

        for(int q=1;q<=qu;q++){
            for(int w=0;w<3;w++){
                dp[q][w]=false;
            }
        }

        dp[0][0]=true;
        for(int q=1;q<=qu;q++){
            for(int w=0;w<3;w++){
                for(int prv=0;prv<3;prv++){
                    int lf=pos[q]-pos[q-1]-1;
                    int rg=pos[q+1]-pos[q]-1;

                    if(dp[q-1][prv]==false)continue;
                    
                    if((w+prv)==lf && w<=rg){
                        dp[q][w]=true;
                        bc[q][w]=prv;
                    }
                    else if((w+prv)<lf && w<=rg){
                        if((lf-w-prv)%2==0 && w+prv>0){
                            dp[q][w]=true;
                            bc[q][w]=prv;
                        }
                    }
                }
            }
        }
        

        if(dp[qu][0]==false){
            cout<<-1<<endl; continue;
        }
        int cur=qu;
        deque<int>ans;
        int grk=0;

        while(cur){
        //    cout<<cur<<" "<<bc[cur][grk]<<endl;
            int lbh=(pos[cur]-pos[cur-1]-1-grk-bc[cur][grk])/2;
            for(int q=1;q<=lbh;q++){
                ans.push_front(pos[cur-1]+1+lbh);
            }

            grk=bc[cur][grk]; 
            cur--;
            for(int q=1;q<=grk;q++){
                ans.push_back(pos[cur]);
            }
        }
        cout<<ans.size()<<endl;
        for(auto x : ans){
            cout<<x<<" ";
        }
        cout<<endl;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30