Submission #1258904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258904		arashmemar	JOIRIS (JOI16_joiris)	C++20	0 / 100	1095 ms	320 KiB

joiris

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100;

bool a[2 * maxn][maxn];
int r[maxn];
int mx;

vector <pair <int, int>> ops;

int n, k;

void sh(int ind)
{
	for (int j = 1;j <= n;j++)
	{
		r[j] = 0;
	}
	mx = 0;
	for (int i = ind;i < maxn - 1;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			a[i][j] = a[i + 1][j];
			mx = max(mx, r[j]);
		}
	}
	for (int i = 1;i < maxn;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			if (a[i][j])
			{
				r[j] = i;
			}
		}
	}
	return ;
}

int fh(int x)
{
	int ind = 0;
	for (int i = maxn - 1;i;i--)
	{
		if (a[i][x])
		{
			ind = i;
			break;
		}
	}
	return ind;
}

bool check()
{
	bool ret = 0;
	for (int i = 1;i < maxn;i++)
	{
		bool d = 1;
		for (int j = 1;j <= n;j++)
		{
			d &= a[i][j];
		}
		if (d)
		{
			sh(i);
			check();
			ret = 1;
		}
	}
	return ret;
}

bool add(int t, int x)
{
	ops.push_back({t, x});
	if (t == 1)
	{
		int ind = fh(x) + 1;
		for (int i = ind;i < ind + k;i++)
		{
			a[i][x] = 1;
		}
		r[x] += k;
		mx = max(r[x], mx);
	}
	else
	{
		int ind = 0;
		for (int i = x;i < x + k;i++)
		{
			ind = max(ind, fh(i));
		}
		for (int i = x;i < x + k;i++)
		{
			a[ind + 1][i] = 1;
			r[i] = ind + 1;
		}
		mx = max(mx, ind + 1);
	}

	bool ret = check();
	return ret;
}

void s(bool x = 0)
{
	while (mx >= k)
	{
		for (int i = 1;i <= n;i++)
		{
			if (r[i] == 0 or (r[i] < k and x))
			{
				if (add(1, i))
				{
					break;
				}
			}
		}
	}
	return ;
}

void solve()
{
	if (mx == 0)
	{
		return ;
	}
	s();
	for (int i = 2;i < n;i++)
	{
		if (r[i] != r[i - 1])
		{
			add(2, i);
			s(1);
		}
	}

	if (mx == 0)
	{
		cout << ops.size() << endl;
		for (auto o : ops)
		{
			cout << o.first << ' ' << o.second << endl;
		}
		return ;
	}


	if (mx == 1 and n % 2 == 0)
	{
		cout << -1;
		return ;
	}

	if (r[n] == 0)
	{
		add(1, n);
	}
	for (int i = 1;i <= n / 2;i++)
	{
		add(2, i * 2 - 1);
	}
	cout << ops.size() << endl;
	for (auto o : ops)
	{
		cout << o.first << ' ' << o.second << endl;
	}
	return ;
}


int main()
{
	cin >> n >> k;
	for (int i = 1;i <= n;i++)
	{
		int inp;
		cin >> inp;
		for (int j = 1;j <= inp;j++)
		{
			a[j][i] = 1;
		}
		r[i] = inp;
		mx = max(mx, inp);
	}
	solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55