Submission #589497

#	Time	Username	Problem	Language	Result	Execution time	Memory
589497		Radewoosh	Coins (LMIO19_monetos)	C++14	100 / 100	923 ms	212300 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;
const int inf=1e9;
 
int t, k1, k2;
int n;
 
int tab[nax][nax];
int kosz[nax][nax];
 
int zera;
 
int active[nax][nax];
 
int wz[nax][nax];
int opti[nax][nax];
 
vector<pair<int,pii>> dp[nax][nax];
 
int wazne[nax*nax];
pii tso[nax*nax];
vi lis;
 
void mini(pii &a, pii b)
{
	a=min(a, b);
}
 
int solve()
{
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			dp[i][j]={};
	dp[0][n].push_back({0, {-inf, 0}});
	for (int i=0; i<=n; i++)
	{
		for (int j=n; j>=0; j--)
		{
			if (!active[i][j])
				continue;
			if (i==0 && j==n)
				continue;
			lis.clear();
			if (i)
			{
				for (auto l : dp[i-1][j])
				{
					int x=l.first+j;
					int y=l.second.first+kosz[i][j];
					if (!wazne[x])
					{
						wazne[x]=1;
						tso[x]={inf, 0};
						lis.push_back(x);
					}
					mini(tso[x], {y, 0});
				}
			}
			if (j<n)
			{
				for (auto l : dp[i][j+1])
				{
					int x=l.first;
					int y=l.second.first;
					if (!wazne[x])
					{
						wazne[x]=1;
						tso[x]={inf, 0};
						lis.push_back(x);
					}
					mini(tso[x], {y, 1});
				}
			}
			dp[i][j].resize(lis.size());
			int id=0;
			for (int l : lis)
			{
				wazne[l]=0;
				dp[i][j][id++]={l, tso[l]};
			}
		}
	}
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			opti[i][j]=0;
	pii a{inf, 0};
	pii b{inf, 0};
	for (auto i : dp[n][0])
	{
		if (i.first<=zera)
			a=min(a, {zera-i.first, i.second.first});
		if (i.first>=zera)
			b=min(b, {i.first-zera, i.second.first});
	}
	opti[0][n]=1;
	for (int h : {zera-a.first, zera+b.first})
	{
		if (abs(h)>inf/2)
		{
			debug() << "skip";
			continue;
		}
		int x=n;
		int y=0;
		int v=h;
		while(x>0 || y<n)
		{
			opti[x][y]=1;
			pii wez;
			for (auto i : dp[x][y])
				if (i.first==v)
					wez=i.second;
			if (wez.second)
			{
				y++;
			}
			else
			{
				v-=y;
				x--;
			}
		}
	}
	debug() << imie(dp[n][0].size());
	if (a.first)
		return -1;
	return a.second;
}
 
int rx[]={-1, 1, 0, 0};
int ry[]={0, 0, -1, 1};
 
void relax(int a, int b)
{
	for (int i=0; i<4; i++)
	{
		int x=a+rx[i];
		int y=b+ry[i];
		if (x>=0 && y>=0)
			active[a][b]=max(active[a][b], active[x][y]-1);
	}
}
 
void opti_to_active(int v)
{
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			active[i][j]=(opti[i][j]*v);
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			relax(i, j);
	for (int i=n; i>=0; i--)
		for (int j=n; j>=0; j--)
			relax(i, j);
}
 
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=1; i<=n; i++)
	{
		int x=0;
		for (int j=1; j<=n; j++)
			if (!tab[i][j])
				x++;
		kosz[i][0]=x;
		for (int j=1; j<=n; j++)
		{
			x-=(tab[i][j]==0);
			x+=(tab[i][j]==1);
			kosz[i][j]=x;
		}
	}
	set<int> px, py;
	for (int h=0; h<2; h++)
	{
		py=px;
		px.clear();
		const int d=25;
		for (int j=0; j<=d; j++)
			px.insert(n*j/d);
	}
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			active[i][j]=0;
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			if (px.count(i) || py.count(j))
				active[i][j]=1;
	int ost=solve();
	for (int h=1; h<=1+5*(n>50); h++)
	{
		opti_to_active(5+2*(ost>-1)+(n<=50)*10);
		ost=solve();
	}
	for (int i=1; i<=n; i++)
	{
		int x=0;
		for (int j=n; j; j--)
		{
			if (opti[i][j])
				x=1;
			wz[i][j]=x;
		}
	}
	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:212:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |  scanf("%d%d%d%d", &t, &n, &k1, &k2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:217:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |    scanf("%d", &tab[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100