Submission #956638

#	Time	Username	Problem	Language	Result	Execution time	Memory
956638		nguyennh	Red-blue table (IZhO19_stones)	C++14	27 / 100	1061 ms	860 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{
  const int N = 1e3 + 5;
  
  char a[N][N];
  int pos = 1 , parity = 1;
  vector<int> up;
  deque<pair<int , int>> fix;
  vector<pair<int , int>> need_fix;
  
  void init(){
    pos = 1 , parity = 1;
    up.clear();
    fix.clear();
    need_fix.clear();
  }
  
  void solve(){
    init();
    if (n < m){
      int need = n / 2 + 1;
      for ( int i = 1 ; i <= need ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
          a[i][j] = '-';
        }
      }
      for ( int i = need + 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) a[i][j] = '+';
      }
      for ( int i = need + 1 ; i <= n ; i++ ){
        if (parity & 1){
          for ( int j = 1 ; j <= m / 2 + 1 ; j++ ) swap(a[i][j] , a[pos][j]);
        }
        else {
          for ( int j = m ; j > m - (m / 2 + 1) ; j-- ) swap(a[i][j] , a[pos][j]);
        }
        parity++;
        pos++;
      }
      for ( int i = need + 1 ; i <= n ; i += 2 ){
        if (i + 1 > n) break;
        for ( int j = 1 ; j <= m / 2 + 1 ; j++ ) swap(a[i][j] , a[i + 1][j]);
      }
      for ( int i = need + 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
          if (a[i][j] == '+'){
            up.push_back(i);
            break;
          }
        }
      }
      for ( int i = 1 ; i <= n ; i++ ){
        bool check = true;
        for ( int j = 1 ; j <= m ; j++ ){
          if (a[i][j] == '+'){
            check = false;
            break;
          }
        }
        if (check && up.size()){
          if (up.back() <= i) break;
          for ( int j = 1 ; j <= m ; j++ ) swap(a[i][j] , a[up.back()][j]);
          up.pop_back();
        }
      }
      for ( int i = 1 ; i <= n ; i++ ){
        int cnt = 0;
        for ( int j = 1 ; j <= m ; j++ ) cnt += a[i][j] == '+';
        if (cnt > m / 2 + 1) fix.push_back(make_pair(cnt , i));
        else if (cnt < m / 2 + 1) need_fix.push_back(make_pair(cnt , i));
      }
      sort(need_fix.begin() , need_fix.end() , greater<pair<int , int>>());
      for ( int i = 0 ; i < need_fix.size() ; i++ ){
        if (fix.empty()) break;
        int remain = m / 2 + 1 - need_fix[i].first;
        while (!fix.empty()){
          if (!remain) break;
          while (fix.size() && fix.front().first == m / 2 + 1){
            fix.pop_front();
          }
          pair<int , int> top = fix.front();
          for ( int j = 1 ; j <= m ; j++ ){
            if (!remain || top.first == m / 2 + 1) break;
            if (a[need_fix[i].second][j] == '-' && a[top.second][j] == '+'){
              swap(a[need_fix[i].second][j] , a[top.second][j]);
              remain--;
              top.first--;
            }
          }
          fix.pop_front();
          fix.push_back(top);
        }
      }
      int row = 0 , col = 0;
      for ( int u = 1 ; u <= n ; u++ ){
        int red = 0 , blue = 0;
        for ( int v = 1 ; v <= m ; v++ ){
          if (a[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 (a[u][v] == '+') red++;
          else blue++;
        }
        if (blue > red) col++;
      }
      cout << row + col << el;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) cout << a[i][j];
        cout << el;
      }
    }
    else {
      int need = m / 2 + 1;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= need ; j++ ){
          a[i][j] = '+';
        }
      }
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = need + 1 ; j <= m ; j++ ) a[i][j] = '-';
      }
      for ( int j = need + 1 ; j <= m ; j++ ){
        if (parity & 1){
          for ( int i = 1 ; i <= n / 2 + 1 ; i++ ){
            swap(a[i][j] , a[i][pos]);
          }
        }
        else {
          for ( int i = n ; i > n - (n / 2 + 1) ; i-- ) swap(a[i][j] , a[i][pos]);
        }
        parity++;
        pos++;
      }
      for ( int j = need + 1 ; j <= m ; j += 2 ){
        if (j + 1 > m) break;
        for ( int i = 1 ; i <= n / 2 + 1 ; i++ ) swap(a[i][j] , a[i][j + 1]);
      }
      for ( int j = need + 1 ; j <= m ; j++ ){
        for ( int i = 1 ; i <= n ; i++ ){
          if (a[i][j] == '-'){
            up.push_back(j);
            break;
          }
        }
      }
      for ( int j = 1 ; j <= m ; j++ ){
        bool check = true;
        for ( int i = 1 ; i <= n ; i++ ){
          if (a[i][j] == '-'){
            check = false;
            break;
          }
        }
        if (check && up.size()){
          if (up.back() <= j) break;
          for ( int i = 1 ; i <= n ; i++ ) swap(a[i][j] , a[i][up.back()]);
          up.pop_back();
        }
      }
      for ( int j = 1 ; j <= m ; j++ ){
        int cnt = 0;
        for ( int i = 1 ; i <= n ; i++ ) cnt += a[i][j] == '-';
        if (cnt > n / 2 + 1) fix.push_back(make_pair(cnt , j));
        else if (cnt < n / 2 + 1) need_fix.push_back(make_pair(cnt , j));
      }
      sort(need_fix.begin() , need_fix.end() , greater<pair<int , int>>());
      for ( int i = 0 ; i < need_fix.size() ; i++ ){
        if (fix.empty()) break;
        int remain = n / 2 + 1 - need_fix[i].first;
        while (!fix.empty()){
          if (!remain) break;
          while (fix.size() && fix.front().first == n / 2 + 1){
            fix.pop_front();
          }
          pair<int , int> top = fix.front();
          for ( int j = 1 ; j <= n ; j++ ){
            if (!remain || top.first == n / 2 + 1) break;
            if (a[j][need_fix[i].second] == '+' && a[j][top.second] == '-'){
              swap(a[j][need_fix[i].second] , a[j][top.second]);
              remain--;
              top.first--;
            }
          }
          fix.pop_front();
          fix.push_back(top);
        }
      }
      int row = 0 , col = 0;
      for ( int u = 1 ; u <= n ; u++ ){
        int red = 0 , blue = 0;
        for ( int v = 1 ; v <= m ; v++ ){
          if (a[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 (a[u][v] == '+') red++;
          else blue++;
        }
        if (blue > red) col++;
      }
      cout << row + col << el;
      for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ) cout << a[i][j];
        cout << el;
      }
    }
  }
}

signed main (){
//  freopen("redblue.inp" , "r" , stdin);
//  freopen("redblue.out" , "w" , stdout);
  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;
//      return 0;
    }
    sub_test::solve();
  }
}

Compilation message (stderr)

stones.cpp: In function 'void sub_test::solve()':
stones.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |       for ( int i = 0 ; i < need_fix.size() ; i++ ){
      |                         ~~^~~~~~~~~~~~~~~~~
stones.cpp:246:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |       for ( int i = 0 ; i < need_fix.size() ; i++ ){
      |                         ~~^~~~~~~~~~~~~~~~~

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