oj.uz

Submission #329126

# Submission time Handle Problem Language Result Execution time Memory
329126 2020-11-19T10:40:50 Z mat_v Red-blue table (IZhO19_stones) C++14
100 / 100
 81 ms 9452 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int mat[1005][1005];
int ans[1005][1005];
pii val[1005];
bool da[1005];
int n,m;


void solve(){
    cin >> n >> m;
    if(n == 1){
        cout << m << "\n";
        ff(i,1,m)cout << '-';
        cout << "\n";
        return;
    }
    if(m == 1){
        cout << n << "\n";
        ff(i,1,n)cout << "+\n";
        return;
    }
    bool o = 0;
      if(n > m){
        swap(n,m);
        o = 1;
    }
    int p1 = 0;
    int p2 = m;

    ff(i,1,m)val[i] = {0,i};
    ff(i,1,m)da[i] = 0;
    vector<int> izb;



    ff(i,1,n){
        sort(val + 1, val + m + 1);
        int br = (m+2)/2;
        br -= (izb.size());
        ff(j,1,br){
            val[j].xx++;
        }
        ff(j,1,m){
            if(val[j].xx > (n-1)/2 && da[val[j].yy] == 0){
                da[val[j].yy] = 1;
                val[j].xx = 1e9;
                izb.pb(val[j].yy);
            }
        }
        int tr2 = m - (izb.size());
        //cout << i << " " << tr2 << "\n";
        if(tr2 + i > p1 + p2){
            p1 = i;
            p2 = tr2;
        }
    }
    if(p1 == 0){
        if(o){
            swap(n,m);
        }
        cout << max(n,m) << "\n";
        ff(i,1,n){
            ff(j,1,m){
                if(n > m)cout << '+';
                else cout << '-';
            }
            cout << "\n";
        }
        return;
    }
    //cout << p1 << " " << p2 << "\n";
    cout << p1 + p2 << "\n";
    ff(i,1,n){
        ff(j,1,m)mat[i][j] = 0;
    }
    ff(i,1,m)val[i] = {0,i};
    izb.clear();
    ff(i,1,m)da[i] = 0;
    ff(i,1,n){
        sort(val + 1, val + m + 1);
        int br = (m+2)/2;
        br -= (izb.size());
        for(auto c:izb){
            mat[i][c] = 1;
        }
        ff(j,1,br){
            mat[i][val[j].yy] = 1;
            val[j].xx++;
        }
        ff(j,1,m){
            if(val[j].xx > (n-1)/2 && da[val[j].yy] == 0){
                da[val[j].yy] = 1;
                val[j].xx = 1e9;
                izb.pb(val[j].yy);
            }
        }
        int tr2 = m - (izb.size());
        //cout << i << " " << tr2 << "\n";
        if(tr2 + i == p1 + p2){
           // cout << "aa\n";
            if(o){
                ff(k,1,n){
                    ff(r,1,m){
                        ans[r][k] = mat[k][r]^1;
                        //ans[r][k] = ans[k][r];
                    }
                }
                swap(n,m);
            }
            else{
                ff(k,1,n){
                    ff(r,1,m){
                        ans[k][r] = mat[k][r];
                    }
                }
            }

            ff(k,1,n){
                ff(r,1,m){
                    if(ans[k][r] == 1)cout << '+';
                    else cout << '-';
                }
                cout << "\n";
            }
            return;
        }
    }

}

int main()
{

    //ios_base::sync_with_stdio(false); cin.tie(0);

    int t;
    cin >> t;
    while(t--)solve();

    return 0;
}

Compilation message

stones.cpp: In function 'void solve()':
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:34:9: note: in expansion of macro 'ff'
   34 |         ff(i,1,m)cout << '-';
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:40:9: note: in expansion of macro 'ff'
   40 |         ff(i,1,n)cout << "+\n";
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:51:5: note: in expansion of macro 'ff'
   51 |     ff(i,1,m)val[i] = {0,i};
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:52:5: note: in expansion of macro 'ff'
   52 |     ff(i,1,m)da[i] = 0;
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:57:5: note: in expansion of macro 'ff'
   57 |     ff(i,1,n){
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:61:9: note: in expansion of macro 'ff'
   61 |         ff(j,1,br){
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:64:9: note: in expansion of macro 'ff'
   64 |         ff(j,1,m){
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:83:9: note: in expansion of macro 'ff'
   83 |         ff(i,1,n){
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:84:13: note: in expansion of macro 'ff'
   84 |             ff(j,1,m){
      |             ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:94:5: note: in expansion of macro 'ff'
   94 |     ff(i,1,n){
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:95:9: note: in expansion of macro 'ff'
   95 |         ff(j,1,m)mat[i][j] = 0;
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:97:5: note: in expansion of macro 'ff'
   97 |     ff(i,1,m)val[i] = {0,i};
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:99:5: note: in expansion of macro 'ff'
   99 |     ff(i,1,m)da[i] = 0;
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:100:5: note: in expansion of macro 'ff'
  100 |     ff(i,1,n){
      |     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:107:9: note: in expansion of macro 'ff'
  107 |         ff(j,1,br){
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:111:9: note: in expansion of macro 'ff'
  111 |         ff(j,1,m){
      |         ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:123:17: note: in expansion of macro 'ff'
  123 |                 ff(k,1,n){
      |                 ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'r' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:124:21: note: in expansion of macro 'ff'
  124 |                     ff(r,1,m){
      |                     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:132:17: note: in expansion of macro 'ff'
  132 |                 ff(k,1,n){
      |                 ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'r' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:133:21: note: in expansion of macro 'ff'
  133 |                     ff(r,1,m){
      |                     ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:139:13: note: in expansion of macro 'ff'
  139 |             ff(k,1,n){
      |             ^~
stones.cpp:6:27: warning: unnecessary parentheses in declaration of 'r' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
stones.cpp:140:17: note: in expansion of macro 'ff'
  140 |                 ff(r,1,m){
      |                 ^~

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 5 ms 620 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2156 KB Output is correct
2 Correct 74 ms 7308 KB Output is correct
3 Correct 68 ms 7916 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2540 KB Output is correct
2 Correct 66 ms 6892 KB Output is correct
3 Correct 62 ms 5612 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 5 ms 620 KB Output is correct
5 Correct 73 ms 2156 KB Output is correct
6 Correct 74 ms 7308 KB Output is correct
7 Correct 68 ms 7916 KB Output is correct
8 Correct 73 ms 2540 KB Output is correct
9 Correct 66 ms 6892 KB Output is correct
10 Correct 62 ms 5612 KB Output is correct
11 Correct 21 ms 876 KB Output is correct
12 Correct 63 ms 6380 KB Output is correct
13 Correct 66 ms 6764 KB Output is correct
14 Correct 49 ms 5484 KB Output is correct
15 Correct 81 ms 9452 KB Output is correct
16 Correct 58 ms 7404 KB Output is correct
17 Correct 28 ms 5228 KB Output is correct