oj.uz

Submission #519731

# Submission time Handle Problem Language Result Execution time Memory
519731 2022-01-27T07:50:07 Z Dasha_Gnedko Red-blue table (IZhO19_stones) C++17
100 / 100
 179 ms 9156 KB 
#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

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

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 5e5 + 100;
const int M = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;

int solve1(vector < vector < int > > &a)
{
    int n = sz(a), m = sz(a[0]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            a[i][j] = 0;
    set < pair < int, int > > st;
    int mx = n / 2 + 1, need = m / 2 + 1, ans = m;
    for(int j = 0; j < m; j++)
        if (n != mx) st.insert({n, j});
    for(int i = 0; i < n; i++)
    {
        if (sz(st) < need) break;
        ans++;
        vector < pair < int, int > > ve;
        for(int j = 0; j < need; j++)
        {
            ve.pb(*st.rbegin());
            st.erase(*st.rbegin());
        }
        for(auto to: ve)
        {
            a[i][to.S] = 1;
            if (to.F == mx + 1) continue;
            st.insert({to.F - 1, to.S});
        }
    }
    return ans;
}

int solve2(vector < vector < int > > &a)
{
    int n = sz(a), m = sz(a[0]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            a[i][j] = 1;
    set < pair < int, int > > st;
    int mx = m / 2 + 1, need = n / 2 + 1, ans = n;
    for(int i = 0; i < n; i++)
        if (m != mx) st.insert({m, i});
    for(int j = 0; j < m; j++)
    {
        if (sz(st) < need) break;
        ans++;
        vector < pair < int, int > > ve;
        for(int i = 0; i < need; i++)
        {
            ve.pb(*st.rbegin());
            st.erase(*st.rbegin());
        }
        for(auto to: ve)
        {
            a[to.S][j] = 0;
            if (to.F == mx + 1) continue;
            st.insert({to.F - 1, to.S});
        }
    }
    return ans;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector < vector < int > > a(n, vector < int > (m, 0)), b = a;
    int v1 = solve1(a), v2 = solve2(b);
    if (v1 < v2)
    {
        v1 = v2;
        a = b;
    }
    cout << v1 << endl;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << (a[i][j] ? "+" : "-");
        cout << endl;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int T;
    cin >> T;
    while (T--)
        solve();
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1384 KB Output is correct
2 Correct 156 ms 6496 KB Output is correct
3 Correct 167 ms 6872 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1520 KB Output is correct
2 Correct 142 ms 5208 KB Output is correct
3 Correct 141 ms 3620 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 144 ms 1384 KB Output is correct
6 Correct 156 ms 6496 KB Output is correct
7 Correct 167 ms 6872 KB Output is correct
8 Correct 140 ms 1520 KB Output is correct
9 Correct 142 ms 5208 KB Output is correct
10 Correct 141 ms 3620 KB Output is correct
11 Correct 30 ms 540 KB Output is correct
12 Correct 140 ms 4484 KB Output is correct
13 Correct 143 ms 3392 KB Output is correct
14 Correct 100 ms 2424 KB Output is correct
15 Correct 179 ms 9156 KB Output is correct
16 Correct 135 ms 6852 KB Output is correct
17 Correct 57 ms 3352 KB Output is correct