結果

問題 No.381 名声値を稼ごう Extra
ユーザー motimoti
提出日時 2016-06-18 00:19:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,508 bytes
コンパイル時間 1,446 ms
コンパイル使用メモリ 122,700 KB
実行使用メモリ 22,212 KB
最終ジャッジ日時 2024-04-18 02:13:05
合計ジャッジ時間 11,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>
#include <fstream>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int sz;

vector<int> to_vector(string s) {
  vector<int> ret;
  sz = max(sz, (int)s.size() + 1);
  reverse(all(s));
  for(auto c: s) {
    ret.push_back(c);
  }
  ret.resize(sz, inf);
  return ret;
}

bool is_zero(vector<int>& v) {
  if(v[0] != 0) return false;
  if(v.size() > 1 && v[1] != inf) return false;
  return true;
}

void divide_by_2(vector<int>& v) {
  rep(i, v.size()) {
    if(v[i] < inf) {
      v[i] /= 2;
      if(v[i+1] < inf) {
        v[i] += ((v[i+1] * 10) / 2) % 10;
      }
      if(v[i] == 0 && v[i+1] == inf) {
        v[i] = inf;
      }
    }
  }
  if(v[0] == inf) v[0] = 0;
}

void multiply_by_2(vector<int>& v) {
  if(v.back() != inf) v.back() *= 2;
  for(int i=v.size() - 1; i>=1; i--) {
    if(v[i-1] == inf) continue;
    v[i-1] *= 2;
    if(v[i-1] > 10) {
      if(v[i] == inf) v[i] = 0;
      v[i] += v[i-1] / 10;
      v[i-1] %= 10;
    }
  }
}

void add(vector<int>& a, vector<int>& b) {
  assert(a.size() == b.size());
  rep(i, a.size()) {
    a[i] += b[i];
    if(a[i] > 10) {
      if(a[i+1] == inf) a[i+1] = 0;
      a[i+1] += a[i] / 10;
      a[i] %= 10;
    }
  }
}

void minus_by(vector<int>& a, vector<int>& b) {
  assert(a.size() == b.size());
  rep(i, a.size()) {
    if(b[i] == inf) continue;
    a[i] -= b[i];
    if(a[i] < 0) {
      a[i] += 10;
      a[i+1] --;
    }
  }

  for(int i=a.size() - 1; i>=0; i--) {
    if(a[i] == inf) continue;
    else if(a[i] == 0) a[i] = inf;
    else break;
  }
  if(a[0] == inf) a[0] = 0;
}

vector<int> dfs(vector<int>& N) {
  if(is_zero(N)) return vector<int>(sz);
  auto n1 = N; divide_by_2(n1);
  auto n2 = N; multiply_by_2(n2);
  return max(dfs(n1), n2);
}

template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { ost << "["; rep(i, v.size()) { if(i) ost << ", "; ost << v[i]; } ost << "]"; return ost; }

int main() {
/*
  vector<int> a = {3, 2, 1};
  vector<int> b = {3, inf, inf};
  auto c = a;
  multiply_by_2(a);
  cout << a << endl;
  multiply_by_2(a);
  cout << a << endl;
  multiply_by_2(a);
  cout << a << endl;
  multiply_by_2(a);
//  a.resize(a.size() + 1);cout << a << endl;multiply_by_2(a);
  cout << a << endl;
  exit(0);
  */

  string n; cin >> n; sz = n.size();
  auto N = to_vector(n);
  auto normal = to_vector(n);
  N.resize(sz); normal.resize(sz);
  auto K = N;
  while(!is_zero(K)) {
    divide_by_2(K);
    add(normal, K);
  }

  auto d = dfs(N);
  minus_by(d, normal);
  string s;
  for(auto c: d) {
    if(c != inf)
      s += '0' + c;
  }
  reverse(all(s));
  cout << s << endl;
  for(int i=d.size() - 1; i>=0; i--) cout << d[i] << " "; cout << endl;
  
  return 0;
}
0