Submission #14189

#	Time	Username	Problem	Language	Result	Execution time	Memory
14189		ainu7	Be Two Bees (OJUZ10_b2b)	C++98	33 / 100	1000 ms	8756 KiB

b2b

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mod = 1 << 30;
const int max_radix = 8;

class BigInt {
 public:
  BigInt() {}
  BigInt(long long a) {
    for (int i=0; i<max_radix; i++) {
      digit[i] = a % mod;
      a /= mod;
    }
  }

  void mult(BigInt a) {
    long long d[max_radix] = {0};
    int mmax = 0, a_mmax = 0;
    for (int i=0; i<max_radix; i++)
      if (digit[i]) mmax = i;
    for (int i=0; i<max_radix; i++)
      if (a.digit[i]) a_mmax = i;

    for (int i=0; i<=mmax; i++)
      for (int j=0; j<=a_mmax && j<max_radix-i; j++) {
        d[i+j] += digit[i] * a.digit[j];
        d[i+j+1] += d[i+j] / mod;
        d[i+j] %= mod;
      }

    for (int i=0; i<max_radix; i++)
      digit[i] = d[i];
  }

  void mult(int a) {
    for (int i=max_radix-1; i>=0; i--) {
      digit[i] *= a;
      if (digit[i] >= mod) { digit[i+1] += digit[i] / mod; digit[i] %= mod; }
    }
  }

  void add(BigInt a) {
    for (int i=max_radix-1; i>=0; i--) {
      digit[i] += a.digit[i];
      if (digit[i] >= mod) { digit[i] -= mod; digit[i+1] ++; }
    }
  }

  bool bigger(BigInt a) {
    for (int i=max_radix-1; i>=0; i--) {
      if (digit[i] > a.digit[i]) return true;
      if (digit[i] < a.digit[i]) return false;
    }

    return false;
  }

  void print() {
    for (int i=0; i<max_radix; i++) printf("%lld ", digit[i]); printf("\n");
  }

  double convert() {
    double ret = 0.0;
    for (int i=max_radix-1; i>=0; i--) {
      ret *= mod;
      ret += digit[i];
    }
    return ret;
  }

 private:
  long long digit[max_radix];
};

bool is_bigger(BigInt u1, int d1, BigInt u2, int d2) {
  u1.mult(d2);
  u2.mult(d1);
  return u1.bigger(u2);
}

BigInt HT[100000];

int main()
{
  int N;
  cin >> N;

  vector<int> H(N), T(N);
  long long sum = 0;
  for (int i=0; i<N; i++) {
    cin >> H[i];
    sum += H[i];
  }
  for (int i=0; i<N; i++) {
    cin >> T[i];
    HT[i] = BigInt(1LL * H[i] * T[i]);
  }


  BigInt ll(0);
  BigInt rr(1LL << 50);
  BigInt down(1);

  int idx1, idx2;
  for (int iter = 0; iter < 120; iter ++) {
//    printf("%d\n", iter);
    BigInt mid = ll;
    mid.add(rr);
    ll.mult(BigInt(2));
    rr.mult(BigInt(2));
    down.mult(BigInt(2));

/*    mid.print();
    down.print();
    printf("%f\n", mid.convert() / down.convert());*/

    // T = mid / down

    idx1 = -1, idx2 = -1;
    BigInt i1_up/*, i1_down*/, i2_up/*, i2_down*/;
    for (int i=0; i<N; i++) {
      // (mid + H[i] * down * T[i]) / (down * T[i])
      BigInt now_up = HT[i];
      now_up.mult(down);
      now_up.add(mid);
     
//      BigInt now_down = down;
//      now_down.mult(T[i]);
//      BigInt now_down(T[i]);

      if (idx1 == -1 || is_bigger(now_up, T[i], i1_up, T[idx1])) {
        i2_up = i1_up;
//        i2_down = i1_down;
        i1_up = now_up;
//        i1_down = now_down;
        idx2 = idx1;
        idx1 = i;
      } else if (idx2 == -1 || is_bigger(now_up, T[i], i2_up, T[idx2])) {
        i2_up = now_up;
//        i2_down = now_down;
        idx2 = i;
      }
    }

    BigInt leq(sum);
    leq.mult(T[idx1]);
    leq.mult(T[idx2]);
    leq.mult(down);

    BigInt req = i1_up;
    req.mult(T[idx2]);
    BigInt req2 = i2_up;
    req2.mult(T[idx1]);
    req.add(req2);

    if (leq.bigger(req)) ll = mid; else rr = mid;
  }

  if (idx1 > idx2) swap(idx1, idx2);
  cout << idx1 + 1 << " " << idx2 + 1 << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 28
• Subtask 4: 0 / 39