Submission #1319974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319974		Petrix	DEL13 (info1cup18_del13)	C++20	100 / 100	7 ms	2236 KiB

del13

#include <iostream>
#include <vector>

using namespace std;
int dp[150000][3],p[150000][3],v[150000];
vector<int> a1,a2;

void solve(){
	int n,q,i,j,k,aux1,aux2,aux=0,mar;
	cin>>n>>q;
	for(i=1;i<=q;i++) cin>>v[i];
	q++;v[q]=n+1;v[q+1]=n+2;
	for(i=0;i<=q+2;i++){
        dp[i][0]=dp[i][1]=dp[i][2]=0;
	}
    dp[0][0]=1;
	for(i=1;i<=q;i++){
		for(j=0;j<3;j++){
			for(k=0;k<3;k++){
				aux1=v[i]-v[i-1]-1;
				aux2=v[i+1]-v[i]-1;
				if((j+k==aux1 && k<=aux2) ||
                (j+k<aux1 && (aux1-j+k)%2==0 && k<=aux2 && j+k>0)){
					if(!dp[i][k] && dp[i-1][j]==1){
						p[i][k]=j;dp[i][k]=1;
					}
				}

			}
		}
	}

	if(!dp[q][0]){
		cout<<"-1\n";
		return;
	}
	a1.clear();a2.clear();
	aux=0;
	while(q){
		for(i=0;i<aux;i++) a1.push_back(v[q]);
		mar=(v[q]-v[q-1]-1-aux-p[q][aux])/2;
		for(i=1;i<=mar;i++) a2.push_back(v[q-1]+mar+1);
		aux=p[q][aux];q--;
	}
	cout<<a1.size()+a2.size()<<"\n";
	for(auto it:a2) cout<<it<<" ";
	for(auto it:a1) cout<<it<<" ";
	cout<<"\n";
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int t;cin>>t;
	while(t){t--;
		solve();
	}
}

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