結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー 👑 p-adic
提出日時 2022-08-20 23:27:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,194 bytes
コンパイル時間 654 ms
実行使用メモリ 10,184 KB
スコア 0
最終ジャッジ日時 2022-08-20 23:27:24
合計ジャッジ時間 6,227 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using uint = unsigned int;
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; }

int main()
{
  constexpr const ll N = 100;
  constexpr const ll M = 8;
  constexpr const ll F = 7 * 7 * 7 * 7 * 7 * 7 * 7;
  CIN( ll , N_dummy );
  CIN( ll , M_dummy );
  ll a[M];
  ll b[M];
  ll Linfty_min = 2000 * 8;
  ll P[9] = {};
  ll P_min[9] = {};
  ll length[8];
  ll length_min[8];
  ll num[8] = {};
  ll i_max = 0;
  FOR_LL( i , 0 , M ){
    cin >> a[i] >> b[i];
  }
  FOR_LL( f , 0 , F ){
    bool used[7] = {};
    FOR_LL( i , 1 , 8 ){
      const ll fi = f % 7;
      bool& used_i = used[fi];
      if( used_i ){
	i = 8;
	P[0] = -1;
      } else {
	used_i = true;
	P[i] = fi;
	f /= 7;
      }
    }
    if( P[0] == 0 ){
      ll Linfty = 0;
      ll length_max = 0;
      FOR_LL( i , 0 , 8 ){
	const ll length_i = max( Distance( a[P[i]] , a[P[i+1]] ) , Distance( b[P[i]] , b[P[i+1]] ) );
	length[i] = length_i;
	Linfty += length_i;
	if( length_max < length_i ){
	  length_max = length_i;
	  i_max = i;
	}
      }
      if( Linfty < Linfty_min ){
	Linfty_min = Linfty;
	FOR_LL( i , 1 , 8 ){
	  P_min[i] = P[i];
	  length_min[i] = length[i];
	}
      }
    } else {
      P[0] = 0;
    }
  }

  ll D = Linfty_min / ( N + M );
  ll num_sum = 0;
  FOR_LL( i , 0 , 8 ){
    ll& length_i = length_min[i];
    ll num_i = length_i / D - ( length_i % D == 0 ? 1 : 0 );
    num[i] = num_i;
    num_sum += num_i;
  }
  num[i_max] += M - num_sum;
  FOR_LL( i , 0 , 8 ){
    ll distance = length_min[i] / ( num[i] + 1 );
    ll& ai = a[P_min[i]];
    ll& bi = b[P_min[i]];
    ll& ai_next = a[P_min[i+1]];
    ll& bi_next = b[P_min[i+1]];
    ll d_x = Distance( ai , ai_next );
    ll d_y = Distance( bi , bi_next );
    ll sign_x = ai < ai_next ? 1 : -1;
    ll sign_y = bi < bi_next ? 1 : -1;
    ll& num_i = num[i];
    FOR_LL( j , 0 , num_i ){
      cout << ai + min( d_x , distance * ( j + 1 ) ) * sign_x << " " << bi + min( d_y , distance * ( j + 1 ) ) * sign_y << endl;
    }
  }
    cout << M + N + 1 << endl;
    ll m = 1;
    FOR_LL( i , 0 , 8 ){
      cout << 1 << " " << P_min[i] + 1 << endl;
      ll& num_i = num[i];
      FOR_LL( j , 0 , num_i ){
	cout << 2 << " " << m << endl;
	m++;
      }
    }
    cout << 1 << " " << 1 << endl;
    return 0;
}
0