oj.uz

Submission #955921

# Submission time Handle Problem Language Result Execution time Memory
955921 2024-03-31T17:32:54 Z nguyennh Red-blue table (IZhO19_stones) C++14
0 / 100
 2000 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 348 KB Output is correct
2 Execution timed out 2028 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 348 KB Output is correct
2 Execution timed out 2028 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 344 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 348 KB Output is correct
2 Execution timed out 2028 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -