結果

問題 No.180 美しいWhitespace (2)
コンテスト
ユーザー itezpace
提出日時 2016-08-15 09:13:09
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3,219 ms / 5,000 ms
コード長 1,507 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,174 ms
コンパイル使用メモリ 171,528 KB
実行使用メモリ 31,620 KB
最終ジャッジ日時 2026-03-08 16:07:14
合計ジャッジ時間 7,582 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
  ll n,a,b;
  cin>>n;
  vector<ll> va,vb;
  for(int i=0; i<n; ++i){
    cin>>a>>b;
    va.push_back(a);
    vb.push_back(b);
  }
  ll ma,mi;
  vector<ll> vma,vmi;
  for(int i=0; i<=30; ++i){
    ma=0;
    mi=LLONG_MAX;
    ll ii;
    ii=pow(2,i);
    for(int j=0; j<n; ++j){
      ll c;
      c=va[j]+vb[j]*ii;
      if(c>ma) ma=c;
      if(c<mi) mi=c;
    }
    vma.push_back(ma);
    vmi.push_back(mi);
  }
  ll mid,mii;
  mid=LLONG_MAX;
  mii=LLONG_MAX;
  for(int i=0; i<vma.size(); ++i){
    ll d;
    d=vma[i]-vmi[i];
    if(d<mid){
      mid=d;
      mii=i;
    }
  }
  ll s,e;
  s=pow(2,mii-1);
  e=pow(2,mii+1);
  vector<ll> vma2,vmi2;
  for(int i=s; i<=e; i+=1000){
    ma=0;
    mi=LLONG_MAX;
    for(int j=0; j<n; ++j){
      ll c;
      c=va[j]+vb[j]*i;
      if(c>ma) ma=c;
      if(c<mi) mi=c;
    }
    vma2.push_back(ma);
    vmi2.push_back(mi);
  }
  mid=LLONG_MAX;
  mii=LLONG_MAX;
  for(int i=0; i<vma2.size(); ++i){
    ll d;
    d=vma2[i]-vmi2[i];
    if(d<mid){
      mid=d;
      mii=i;
    }
  }
  mid=LLONG_MAX;
  ll x;
  x=LLONG_MAX;
  for(int i=s+1000*(mii-1); i<=s+1000*(mii+1); ++i){
    ma=0;
    mi=LLONG_MAX;
    if(i>0){
    for(int j=0; j<n; ++j){
      ll c;
      c=va[j]+vb[j]*i;
      if(c>ma) ma=c;
      if(c<mi) mi=c;
    }
    ll d;
    d=ma-mi;
    if(d<mid){
      mid=d;
      x=i;
    }
    }
  }
  cout<<x<<endl;
  return 0;
}
0