oj.uz

Submission #150974

# Submission time Handle Problem Language Result Execution time Memory
150974 2019-09-01T13:24:39 Z leatherman Red-blue table (IZhO19_stones) C++14
100 / 100
 117 ms 5356 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define ll int
#define ld long double
#define endl "\n"
#define fi first
#define se second
#define y1 sadjfskldf
#define PB push_back
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

const ll N = 1005;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll Q,n,m,ans,kol,edd,a[N][N];
set<pair<ll, ll> > s;
set<pair<ll, ll> > :: iterator it;
vector<pair<ll, ll> > v;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>Q;
    while(Q--)
    {
        cin>>n>>m;
        s.clear();
        if(n > m)
        {
            for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = 1;
            for(int i = 1; i <= n; i++) s.insert({m, i});
            ans = n;
            for(int i = 1; i <= m; i++)
            {
                edd = 0;
                kol = n / 2 + 1;
                v.clear();
                for(it = --s.end(); ; --it)
                {
                    if((*it).fi == m / 2 + 1)
                    {
                        edd = 1;
                        break;
                    }
                    v.PB(*it);
                    if(--kol == 0) break;
                    if(it == s.begin()) break;
                }
                if(edd) break;
                for(auto j : v)
                {
                    s.erase(s.find({j.fi, j.se}));
                    s.insert({j.fi - 1, j.se});
                    a[j.se][i] = 0;
                }
                ans++;
            }
        } else
        {
            for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = 0;
            for(int j = 1; j <= m; j++) s.insert({n, j});
            ans = m;
            for(int i = 1; i <= n; i++)
            {
                edd = 0;
                kol = m / 2 + 1;
                v.clear();
                for(it = --s.end(); ; --it)
                {
                    if((*it).fi == n / 2 + 1)
                    {
                        edd = 1;
                        break;
                    }
                    v.PB(*it);
                    if(--kol == 0) break;
                    if(it == s.begin()) break;
                }
                if(edd) break;
                for(auto j : v)
                {
                    s.erase(s.find({j.fi, j.se}));
                    s.insert({j.fi - 1, j.se});
                    a[i][j.se] = 1;
                }
                ans++;
            }
         }
         cout<<ans<<endl;
         for(int i = 1; i <= n; i++)
         {
             for(int j = 1; j <= m; j++) cout<<(a[i][j] ? '+' : '-');
             cout<<endl;
         }
    }

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 6 ms 632 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1808 KB Output is correct
2 Correct 106 ms 4216 KB Output is correct
3 Correct 101 ms 4984 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1912 KB Output is correct
2 Correct 95 ms 4088 KB Output is correct
3 Correct 89 ms 3316 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 99 ms 1808 KB Output is correct
6 Correct 106 ms 4216 KB Output is correct
7 Correct 101 ms 4984 KB Output is correct
8 Correct 100 ms 1912 KB Output is correct
9 Correct 95 ms 4088 KB Output is correct
10 Correct 89 ms 3316 KB Output is correct
11 Correct 22 ms 684 KB Output is correct
12 Correct 91 ms 4296 KB Output is correct
13 Correct 95 ms 4728 KB Output is correct
14 Correct 72 ms 3940 KB Output is correct
15 Correct 117 ms 5356 KB Output is correct
16 Correct 87 ms 4232 KB Output is correct
17 Correct 41 ms 3320 KB Output is correct