Submission #955921

#	Time	Username	Problem	Language	Result	Execution time	Memory
955921		nguyennh	Red-blue table (IZhO19_stones)	C++14	0 / 100	2068 ms	348 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;
  vector<vector<int>> out;

  void backtrack(int i , int j){
    if (i > n && j > m){
      for ( int u = 1 ; u <= n ; u++ ){
        for ( int v = 1 ; v <= m ; v++ ){
          if (x[u][v] == -1) return;
        }
      }
      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);
        }
      }
      return;
    }
    for ( int k = 0 ; k <= 1 ; k++ ){
      x[i][j] = k;
      for ( int dir = 0 ; dir < 4 ; dir++ ){
        int new_i = i + dx[dir];
        int new_j = j + dy[dir];
        if (new_i <= n + 1 && new_j <= m + 1 && new_i >= 1 && new_j >= 1 && x[new_i][new_j] == -1){
          backtrack(new_i , new_j);
        }
      }
    }
    x[i][j] = -1;
  }

  void solve(){
    memset(x , -1 , sizeof(x)); 
    backtrack(1 , 1);
    cout << ans << el;
    for ( auto x : out ){
      for ( auto lmao : x ) cout << (lmao ? '+' : '-');
      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;
     }
  }
}

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