Submission #1318981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318981		Jawad_Akbar_JJ	DEL13 (info1cup18_del13)	C++20	100 / 100	7 ms	2048 KiB

del13

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<17;
int dp[N][3], Par[N][3], a[N];

void solve(){
	int n, q;
	cin>>n>>q;


	for (int i=1;i<=q;i++)
		cin>>a[i];
	a[++q] = n + 1;
	a[q+1] = n + 2;

	for (int i=0;i<=q+2;i++){
		for (int j : {0, 1, 2})
			dp[i][j] = 0;
	}

	dp[0][0] = 1;
	for (int i=1;i<=q;i++){
		for (int j : {0, 1, 2}){
			for (int k : {0, 1, 2}){
				int ms1 = a[i] - a[i-1] - 1, ms2 = a[i+1] - a[i] - 1;
				if ((j + k == ms1 and k <= ms2) or (j + k < ms1 and (ms1 - j + k) % 2 == 0 and j + k > 0 and k <= ms2)){
					if (dp[i][k] == 0 and dp[i - 1][j] == 1)
						Par[i][k] = j, dp[i][k] = 1;
				}
			}
		}
	}

	if (dp[q][0] == 0){
		cout<<-1<<'\n';
		return;
	}
	vector<int> t1, t2;
	int k = 0;
	while (q){
		for (int i=0;i<k;i++)
			t1.push_back(a[q]);
		int sz = (a[q] - a[q - 1] - 1 - k - Par[q][k]) / 2;

		for (int i=1;i<=sz;i++)
			t2.push_back(a[q - 1] + sz + 1);
		k = Par[q][k], q--;
	}

	cout<<t1.size() + t2.size()<<'\n';
	for (int i : t2)
		cout<<i<<' ';
	for (int i : t1)
		cout<<i<<' ';
	cout<<'\n';
}

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

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