Submission #1319114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319114		neonglitch	DEL13 (info1cup18_del13)	C++20	0 / 100	1096 ms	9860 KiB

del13

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N=2e5+10;
int a[N],gap[N];
bool dp[N][200];
pair<int,int> bt[N][200];
set<int> cur[N];
void solve()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<=n+1;i++)cur[i].clear();
	a[0]=0;
	for(int i=1;i<=k+1;i++)
	{
		if(i<=k)
			cin>>a[i];
		else{
			a[i]=n+1;
		}
		gap[i]=a[i]-a[i-1]-1;
		for(int x=a[i-1]+1;x<a[i];x++)cur[i].insert(x);
		// cout<<"At "<<i<<' '<<cur[i].size()<<endl;
	}
	// gap[i]<=2
	for(int i=0;i<=k+1;i++)for(int j=0;j<=n+1;j++)dp[i][j]=0;
	dp[1][gap[1]]=1;
	bt[1][gap[1]]={-1,-1};
	for(int i=1;i<=k+1;i++)
	{
		for(int j=n+1;j>=3;j--)
		{
			if(!dp[i][j])continue;
			dp[i][j-2]|=dp[i][j];
			bt[i][j-2]={i,j};
		}
		for(int j=0;j<=n+1;j++)
		{
			if(!dp[i][j])continue;
			if(j<=gap[i+1])
			{
				dp[i+1][gap[i+1]-j]|=dp[i][j];
				bt[i+1][gap[i+1]-j]={i,j};
			}
			for(int k1=gap[i+1]-2;j<=k1 and gap[i+1]>2;)
			{
				dp[i+1][k1-j]|=dp[i][j];
				bt[i+1][k1-j]={i+1,k1};
				if(k1>2)k1-=2;
				else break;
			}
		}
	}
	if(!dp[k+1][0])
	{
		cout<<-1<<endl;
		return;
	}
	int i=k+1,j=0;
	vector<int> ans;
	while(i!=1 or j!=gap[1])
	{
		int ni=bt[i][j].first,nj=bt[i][j].second;
		// cout<<"From "<<i<<' '<<j<<' '<<ni<<' '<<nj<<endl;
		if(ni==i)
		{
			// cout<<cur[i].size()<<endl;
			cur[i].erase(begin(cur[i]));
			int x=*begin(cur[i]);
			cur[i].erase(begin(cur[i]));
			cur[i].erase(begin(cur[i]));
			ans.push_back(x);
			cur[i].insert(x);
		}
		else{
			for(int p=0;p<nj;p++)
			{
				ans.push_back(a[ni]);
			}
		}
		i=ni,j=nj;
	}
	cout<<ans.size()<<endl;
	for(auto x:ans)cout<<x<<' ';
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

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