Submission #588720

#	Time	Username	Problem	Language	Result	Execution time	Memory
588720		Radewoosh	Coins (LMIO19_monetos)	C++14	20 / 100	2087 ms	1028 KiB

monetos

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=307;

int t, k1, k2;
int n;

int tab[nax][nax];

int zera;

int wz[nax][nax];

int wyn;
vector<pii> n1, n0;

void cons(int a, int b)
{
	if (a<1 || b<1 || a>n || b>n)
		return;
	if (!wz[a][b] && wz[a-1][b] && wz[a][b-1])
		n1.push_back({a, b});
	if (wz[a][b] && !wz[a+1][b] && !wz[a][b+1])
		n0.push_back({a, b});
}

int main()
{
	scanf("%d%d%d%d", &t, &n, &k1, &k2);
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			scanf("%d", &tab[i][j]);
			zera+=!tab[i][j];
		}
	}
	for (int i=0; i<=n; i++)
		wz[i][0]=wz[0][i]=1;
	vector<pii> kol;
	kol.push_back({1, 1});
	for (int h=1; h<=zera; h++)
	{
		swap(kol[rand()%kol.size()], kol.back());
		pii v=kol.back();
		kol.pop_back();
		wz[v.first][v.second]=1;
		if (v.first<n && wz[v.first+1][v.second-1])
			kol.push_back({v.first+1, v.second});
		if (v.second<n && wz[v.first-1][v.second+1])
			kol.push_back({v.first, v.second+1});
	}
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			wyn+=(tab[i][j]==wz[i][j]);
	n1=kol;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			if (wz[i][j] && !wz[i+1][j] && !wz[i][j+1])
				n0.push_back({i, j});
	while(wyn/2>k1)
	{
		//~ debug() << imie(wyn) << " " << n0.size() << " " << n1.size();
		//~ for (int i=1; i<=n; i++)
			//~ debug() << range(wz[i]+1, wz[i]+1+n);
		//~ static int li=3000;
		//~ li--;
		//~ if (!li)
			//~ return 0;
		swap(n0[rand()%n0.size()], n0.back());
		swap(n1[rand()%n1.size()], n1.back());
		pii zero=n0.back();
		pii jede=n1.back();
		if (wz[jede.first][jede.second] || !wz[jede.first-1][jede.second] || !wz[jede.first][jede.second-1])
		{
			n1.pop_back();
			continue;
		}
		if (!wz[zero.first][zero.second] || wz[zero.first+1][zero.second] || wz[zero.first][zero.second+1])
		{
			n0.pop_back();
			continue;
		}
		if (jede.first>=zero.first && jede.second>=zero.second)
			continue;
		int nowy=wyn-(tab[jede.first][jede.second]==0)-(tab[zero.first][zero.second]==1)+(tab[jede.first][jede.second]==1)+(tab[zero.first][zero.second]==0);
		//~ if (nowy>wyn)
		if (nowy>wyn && (rand()%100))
			continue;
		wyn=nowy;
		n0.pop_back();
		n1.pop_back();
		wz[jede.first][jede.second]=1;
		wz[zero.first][zero.second]=0;
		cons(jede.first, jede.second);
		cons(jede.first+1, jede.second);
		cons(jede.first, jede.second+1);
		cons(zero.first, zero.second);
		cons(zero.first-1, zero.second);
		cons(zero.first, zero.second-1);
	}
	
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
			printf("%d ", wz[i][j]^1);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

monetos.cpp: In function 'int main()':
monetos.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d%d%d", &t, &n, &k1, &k2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |    scanf("%d", &tab[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100