結果

問題 No.5002 stick xor
コンテスト
ユーザー 👑 p-adic
提出日時 2022-08-16 18:30:39
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,037 bytes
コンパイル時間 1,032 ms
実行使用メモリ 3,632 KB
スコア 0
最終ジャッジ日時 2022-08-16 18:30:56
合計ジャッジ時間 13,497 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:59:147: 警告: ‘k_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
   59 |   ll L_copy[ K ] , Li , A[ N2 ], i , j , k , l , a , a_bit , black = 0 , N_minus , black_current , black_min , black_preparation , down , j_min , k_min;
      |                                                                                                                                                   ^~~~~
main.cpp:59:139: 警告: ‘j_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
   59 |   ll L_copy[ K ] , Li , A[ N2 ], i , j , k , l , a , a_bit , black = 0 , N_minus , black_current , black_min , black_preparation , down , j_min , k_min;
      |                                                                                                                                           ^~~~~
main.cpp:136:5: 警告: ‘down’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  136 |     if( down == 1 ){
      |     ^~

ソースコード

diff # 

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <iomanip>
#include <algorithm>
using namespace std;

using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;

template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }

class data1
{
public:
  ll m_l;
  ll m_i;
  inline data1( const ll& l = 0 , const ll& i = 0 ) : m_l( l ) , m_i( i ) {}
};

inline bool operator<( const data1& d0 , const data1& d1 ) { return d0.m_l < d1.m_l; }

class data2
{
public:
  ll m_down;
  ll m_j;
  ll m_k;
  ll m_i;
  inline data2( const ll& down = 0 , const ll& j = 0 , const ll& k = 0 , const ll& i = 0 ) : m_down( down ) , m_j( j ) , m_k( k ) , m_i( i ) {}
};

inline bool operator<( const data2& d0 , const data2& d1 ) { return d0.m_i < d1.m_i; }

int main()
{

  GETLINE( dummy );
  // constexpr const ll N = 3;
  // constexpr const ll K = 3;
  constexpr const ll N = 60;
  constexpr const ll K = 500;
  constexpr const ll N2 = N * N;
  vector<data1> L{};
  vector<data2> D{};
  ll L_copy[ K ] , Li , A[ N2 ], i , j , k , l , a , a_bit , black = 0 , N_minus , black_current , black_min , black_preparation , down , j_min , k_min;
  i = 0;
  while( i < K ){
    cin >> l;
    L.push_back( data1( l , i ) );
    L_copy[i] = l;
    ++i;
  }
  sort( L.begin() , L.end() );
  k = 0;
  while( k < N ){
    cin >> a;
    j = 0;
    l = ( k + 1 ) * N - 1;
    while( j < N ){
      a_bit = a % 2;
      a /= 2;
      A[ l - j ] = a_bit;
      black += a_bit;
      ++j;
    }
    ++k;
  }
  // １回ずつの最大化よりもラスト数回分纏めた最大化の方が
  // sort後のL[K-1].m_lなどが大きい時はスコアが上がるが、
  // 面倒なので１回ずつの最大化で諦める
  i = 0;
  while( i < K ){
    Li = L[i].m_l;
    N_minus = N - Li;
    black_preparation = black + Li;
    black_min = N2;
    j = 0;
    // down
    while( j < N ){
      k = 0;
      while( k < N_minus ){
	black_current = black_preparation;
	l = 0;
	while( l < Li ){
	  black_current -= A[ ( k + l ) * N + j ] * 2;
	  ++l;
	}
	if( black_current < black_min ){
	  black_min = black_current;
	  down = 1;
	  j_min = j;
	  k_min = k;
	}
	++k;
      }
      ++j;
    }
    k = 0;
    // right
    while( k < N ){
      j = 0;
      while( j < N_minus ){
	black_current = black_preparation;
	l = 0;
	while( l < Li ){
	  black_current -= A[ k * N + ( j + l ) ] * 2;
	  ++l;
	}
	if( black_current < black_min ){
	  black_min = black_current;
	  down = 0;
	  j_min = j;
	  k_min = k;
	}
	++j;
      }
      ++k;
    }
    black = black_min;
    D.push_back( data2( down , j_min , k_min , L[i].m_i ) );
    l = 0;
    if( down == 1 ){
      while( l < Li ){
	A[ ( k_min + l ) * N + j_min ] = 1 - A[ ( k_min + l ) * N + j_min ];
	++l;
      }
    } else {
      while( l < Li ){
	A[ k_min * N + ( j_min + l ) ] = 1 - A[ k_min * N + ( j_min + l ) ];
	++l;
      }
    }
    ++i;
  }
  sort( D.begin() , D.end() );
  i = 0;
  while( i < K ){
    const data2& d = D[i];
    if( d.m_down == 1 ){
      cout << d.m_k << " "  << d.m_j << " "  << d.m_k + L_copy[i] - 1 << " " << d.m_j;
    } else {
      cout << d.m_k << " "  << d.m_j << " "  << d.m_k << " " << d.m_j + L_copy[i] - 1;
    }
    ++i;
    if( i < K ){
      cout << endl;
    }
  }
  return 0;

}
0