oj.uz

Submission #684511

# Submission time Handle Problem Language Result Execution time Memory
684511 2023-01-21T11:37:48 Z Chal1shkan Red-blue table (IZhO19_stones) C++14
0 / 100
 2000 ms 67788 KB 
# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e6 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

int n, m;
int mx;

int cnt (vector < vector <int> >& a)
{
	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		int cnt[2] = {0};
		for (int j = 0; j < m; ++j)
		{
			cnt[a[i][j]]++;
		}
		if (cnt[1] >= m / 2 + 1)
		{
			res++;
		}
	}
	for (int j = 0; j < m; ++j)
	{
		int cnt[2] = {0};	
		for (int i = 0; i < n; ++i)
		{
			cnt[a[i][j]]++;
		}
		if (cnt[0] >= n / 2 + 1) 
		{
			res++;
		}
	}
	return res;
	// 010
	// 010
	// 000
}

void rec (int id, vector < vector <int> >& a)
{
	if (id == n)
	{
		mx = max(mx, cnt(a));
	}
	else
	{
		for (int mask = 0; mask < (1LL << m); ++mask)
		{
			vector < vector <int> > new_a = a;
			for (int i = 0; i < m; ++i)
			{
				if (mask & (1LL << i))
				{
					new_a[id][i] = 1;
				}
				else
				{
					new_a[id][i] = 0;
				}
			}
			rec(id + 1, new_a);
		}
	}
}

void rec2 (int id, vector < vector <int> >& a)
{
	if (id == n)
	{
		if (cnt(a) == mx)
		{
			for (int i = 0; i < n; ++i)
			{
				for (int j = 0; j < m; ++j)
				{
					cout << a[i][j] << ' ';
				}
				cout << nl;
			}
			cout << nl;
			exit(0);
		}
		return;
	}
	else
	{
		for (int mask = 0; mask < (1LL << m); ++mask)
		{
			vector < vector <int> > new_a = a;
			for (int i = 0; i < m; ++i)
			{
				if (mask & (1LL << i))
				{
					new_a[id][i] = 1;
				}
				else
				{
					new_a[id][i] = 0;
				}
			}
			rec2(id + 1, new_a);
		}
	}
}

void ma1n (/* SABR */)
{
	cin >> n >> m;
	vector < vector <int> > a(n, vector <int>(m, 0));
	rec(0, a);
	cout << mx << nl;
	rec2(0, a);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 5204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 67788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 3028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong answer
2 Halted 0 ms 0 KB -