Submission #1318973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318973		Jawad_Akbar_JJ	DEL13 (info1cup18_del13)	C++20	40 / 100	12 ms	1384 KiB

del13

#include <iostream>

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])
		cout<<0<<"\n\n";
	else
		cout<<-1<<'\n';
}

int main(){
	int t;
	cin>>t;
	while (t--)
		solve();
}

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