Submission #955978

#	Time	Username	Problem	Language	Result	Execution time	Memory
955978		nguyennh	Red-blue table (IZhO19_stones)	C++14	17 / 100	516 ms	1372 KiB

stones

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , -1 , 0 , 1};

int n , m;

namespace sub_trau{
  bool valid_input(){
    return n <= 4 && m <= 4;
  }

  int x[50][50] , ans = 0 , cnt = 0;
  vector<vector<int>> out;

  void backtrack(int i , int j , int c){
    x[i][j] = c;
    cnt++;
    for ( int dir = 0 ; dir < 4 ; dir++ ){
      int new_i = i + dx[dir];
      int new_j = j + dy[dir];
      if (new_i <= n && new_j <= m && new_i >= 1 && new_j >= 1 && x[new_i][new_j] == -1){
        backtrack(new_i , new_j , 1);
        backtrack(new_i , new_j , 0);
      }
    }
    if (cnt == n * m){
      int col = 0 , row = 0;
      for ( int u = 1 ; u <= n ; u++ ){
        int red = 0 , blue = 0;
        for ( int v = 1 ; v <= m ; v++ ){
          if (x[u][v]) red++;
          else blue++;
        }
        if (red > blue) row++;
      }
      for ( int v = 1 ; v <= m ; v++ ){
        int red = 0 , blue = 0;
        for ( int u = 1 ; u <= n ; u++ ){
          if (x[u][v]) red++;
          else blue++;
        }
        if (blue > red) col++;
      }
      if (col + row > ans){
        ans = col + row;
        out.clear();
        for ( int u = 1 ; u <= n ; u++ ){
          vector<int> cur;
          for ( int v = 1 ; v <= m ; v++ ) cur.push_back(x[u][v]);
          out.push_back(cur);
        }
      }
    }
    x[i][j] = -1;
    cnt--;
  }

  void solve(){
    memset(x , -1 , sizeof(x)); 
    cnt = 0;
    ans = 0;
    out.clear();
    backtrack(1 , 1 , 0);
    backtrack(1 , 1 , 1);
    cout << ans << el;
    for ( auto x : out ){
      for ( auto lmao : x ) cout << (lmao ? '+' : '-');
      cout << el;
    }
  }
}

namespace sub_test{
  void solve(){
//    bool dir = false;
    if (n < m){
//      dir = true;
//      swap(n , m);
      vector<vector<char>> ans(n + 5 , vector<char> (m + 5));
      int need = n / 2 + 1;
      for ( int i = 1 ; i <= min(need , n) ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) ans[i][j] = '-';
      }
      for ( int i = min(need + 1 , n) ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) ans[i][j] = '+';
      }
      cout << m + max(0 , n - need) << el;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) cout << ans[i][j];
        cout << el;
      }
    }
    else {
      vector<vector<char>> ans(n + 5 , vector<char> (m + 5));
      int need = m / 2 + 1;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= min(m , need) ; j++ ) ans[i][j] = '+';
      }
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = min(need + 1 , m) ; j <= m ; j++ ) ans[i][j] = '-';
      }
      cout << n + max(0 , m - need) << el;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) cout << ans[i][j];
        cout << el;
      }
    }
  }
}

signed main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while(t--){
    cin >> n >> m;
   if (sub_trau::valid_input()){
     sub_trau::solve();
     continue;
   }
   sub_test::solve();
  }
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 10
• Subtask 3: 0 / 16
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 31