oj.uz

Submission #254127

# Submission time Handle Problem Language Result Execution time Memory
254127 2020-07-29T11:46:01 Z Berted Coins (LMIO19_monetos) C++14
3.08712 / 100
 576 ms 186232 KB 
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <random>
#include <vector>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppp pair<pii, pii>
using namespace std;
const int INF = 1e9;

const int cst = 64;

int t, n, k1, k2, c;
int ar[351][351], ans[351][351];
bool bt[351][351];

vector<ppp> v[100001];
vector<ppp> tp;
vector<int> tp2;
queue<pii> q;

int main()
{
	mt19937 rng(6969420);
	cin >> t >> n >> k1 >> k2;

	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> ar[i][n - j + 1];
			c += ar[i][n - j + 1];
		}
	}
	for (int i = 0; i < n * (n + 1); i++)
	{
		v[i].reserve(2 * cst);
	}
	q.push({0, 0});
	v[0].push_back({{c, 0}, {0, 0}});
	while (q.size())
	{
		pii c = q.front(); q.pop();
		//cout << "COORD : " << c.fst << ", " << c.snd << "\n";

		sort(v[c.fst * (n + 1) + c.snd].begin(), v[c.fst * (n + 1) + c.snd].end());

		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			while (tp.size() && tp.back().fst.fst == x.fst.fst) tp.pop_back();
			while (tp.size() && tp.back().fst.snd <= x.fst.snd) tp.pop_back();
			tp.push_back(x);
		}

		swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();

		if (v[c.fst * (n + 1) + c.snd].size() > cst)
		{
			int k;
			for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
			{
				if (i & 1) tp2.push_back(i);
				else tp.push_back(v[c.fst * (n + 1) + c.snd][i]);
			}
			k -= cst - (v[c.fst * (n + 1) + c.snd].size() + 1) / 2;
			shuffle(tp2.begin(), tp2.end(), rng);
			for (int i = 0; i < k; i++)
			{
				tp.push_back(v[c.fst * (n + 1) + c.snd][tp2[i]]);
			}
			tp2.clear();
			swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();
		}

		/*
		cout << "VECTOR :\n";
		
		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			cout << x.fst.fst << ", " << x.fst.snd << " - " << x.snd.fst << ", " << x.snd.snd << "\n";
		}
		cout << "--\n";
		*/

		if (c.fst + 1 < n)
		{
			for (auto x : v[c.fst * (n + 1) + c.snd])
			{
				if (x.fst.fst >= c.snd)
				{
					v[(c.fst + 1) * (n + 1) + c.snd].push_back({{x.fst.fst - c.snd, x.fst.snd + ar[c.fst + 1][c.snd]}, {c.fst, c.snd}});
				}
			}
			if (!bt[c.fst + 1][c.snd])
			{
				bt[c.fst + 1][c.snd] = 1;
				q.push({c.fst + 1, c.snd});
			}
		}
		if (c.snd + 1 <= n)
		{
			for (auto x : v[c.fst * (n + 1) + c.snd])
			{
				if (x.fst.fst)
				{
					v[c.fst * (n + 1) + c.snd + 1].push_back({{x.fst.fst - 1, x.fst.snd + ar[c.fst][c.snd + 1]}, {c.fst, c.snd}});
				}
			}
			if (!bt[c.fst][c.snd + 1])
			{
				bt[c.fst][c.snd + 1] = 1;
				q.push({c.fst, c.snd + 1});
			}
		}
	}

	int mx = -1, mx2; pii c;
	//assert(::c - mx >= k1);
	for (int i = 0; i <= n; i++)
	{
		for (auto x : v[(n - 1) * (n + 1) + i])
		{
			if (x.fst.snd > mx)
			{
				mx = x.fst.snd;
				mx2 = x.fst.fst;
				c = {n - 1, i};	
			}
		}
	}

	//cout << mx << " " << mx2 << "  " << c.fst << ", " << c.snd << "\n";

	while (c != make_pair(0, 0))
	{
		//cout << "LOL : " <<  c.fst << ", " << c.snd << "\n";
		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			if (x.fst == make_pair(mx2, mx))
			{
				if (x.snd == make_pair(c.fst - 1, c.snd))
				{
					mx = x.fst.snd - ar[c.fst][c.snd];
					mx2 = x.fst.fst + c.snd;
					for (int i = c.snd; i > 0; i--)
					{
						ans[c.fst][i] = 1;
						::c--;
					}
					c = x.snd;
				}
				else
				{
					mx = x.fst.snd - ar[c.fst][c.snd];
					mx2 = x.fst.fst + 1;
					ans[c.fst][c.snd] = 1;
					::c -= (c.snd > 0);
					c = x.snd;
				}
				break;
			}
		}
	}
	/*
	for (int i = 0; i < n; i++)
	{
		for (int j = n; j > 0; j--)
		{
			cout << ans[i][j];
			if (j > 1) cout << " ";
		}
		cout << "\n";
	}
	cout << ::c << "\n";
	*/
	int pv = n;
	for (int i = n - 1; i >= 0 && ::c; i--)
	{
		int cur = 0;
		for (int j = 1; j <= pv && ::c; j++)
		{
			if (ans[i][j] == 1) 
			{
				cur++;
			}
			else 
			{
				ans[i][j] = 1; cur++; ::c--;
			}
		}
		pv = cur;
	}
	// cout << ::c << "\n";
	// assert(::c == 0);

	for (int i = 0; i < n; i++)
	{
		for (int j = n; j > 0; j--)
		{
			cout << ans[i][j];
			if (j > 1) cout << " ";
		}
		cout << "\n";
	}
	return 0;
}

Compilation message

monetos.cpp: In function 'int main()':
monetos.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:68:6: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
    k -= cst - (v[c.fst * (n + 1) + c.snd].size() + 1) / 2;
    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.08712126618 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2944 KB K = 20
2 Incorrect 11 ms 7936 KB K = 607
3 Incorrect 576 ms 186172 KB K = 20654
4 Partially correct 543 ms 186232 KB K = 23035
5 Incorrect 525 ms 186124 KB K = 20754
6 Incorrect 536 ms 186232 KB K = 22438
7 Incorrect 546 ms 186232 KB K = 22787
8 Incorrect 516 ms 186104 KB K = 24616
9 Incorrect 523 ms 186104 KB K = 21925
10 Partially correct 522 ms 186104 KB K = 22589