oj.uz

Submission #684512

# Submission time Handle Problem Language Result Execution time Memory
684512 2023-01-21T11:39:35 Z Chal1shkan Red-blue table (IZhO19_stones) C++14
17 / 100
 2000 ms 1364 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;
bool ok;

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 (ok) return;
	if (id == n)
	{
		if (cnt(a) == mx)
		{
			for (int i = 0; i < n; ++i)
			{
				for (int j = 0; j < m; ++j)
				{
					if (a[i][j] == 0) cout << '-';
					else cout << '+';
				}
				cout << nl;
			}
			cout << nl;
			ok = 1;
		}
		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 */)
{
	ok = 0, mx = 0;
	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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 20 ms 212 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 20 ms 212 KB Output is correct
3 Execution timed out 2096 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 1364 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 2085 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 20 ms 212 KB Output is correct
3 Execution timed out 2096 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -