Submission #955952

#	Time	Username	Problem	Language	Result	Execution time	Memory
955952		nguyennh	Red-blue table (IZhO19_stones)	C++14	0 / 100	540 ms	460 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)); 
    backtrack(1 , 1 , 0);
    backtrack(1 , 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