oj.uz

Submission #955965

# Submission time Handle Problem Language Result Execution time Memory
955965 2024-03-31T18:13:55 Z nguyennh Red-blue table (IZhO19_stones) C++14
17 / 100
 521 ms 464 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 , 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;
    }
  }
}

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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 521 ms 440 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 521 ms 440 KB Output is correct
3 Incorrect 19 ms 464 KB Wrong answer
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 521 ms 440 KB Output is correct
3 Incorrect 19 ms 464 KB Wrong answer
4 Halted 0 ms 0 KB -