Submission #14187

#	Time	Username	Problem	Language	Result	Execution time	Memory
14187		ainu7	Be Two Bees (OJUZ10_b2b)	C++98	11 / 100	1000 ms	2504 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 = 20;

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};
    for (int i=0; i<max_radix; i++)
      for (int j=0; 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 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(const BigInt& u1, const BigInt& d1, const BigInt& u2, const BigInt& d2) {
  BigInt t1 = u1;
  t1.mult(d2);
  BigInt t2 = u2;
  t2.mult(d1);
  return t1.bigger(t2);
}

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];

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

  int idx1, idx2;
  for (int iter = 0; iter < 200; 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(H[i]);
      now_up.mult(down);
      now_up.mult(T[i]);
      now_up.add(mid);
     
      BigInt now_down = down;
      now_down.mult(T[i]);

      if (idx1 == -1 || is_bigger(now_up, now_down, i1_up, i1_down)) {
        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, now_down, i2_up, i2_down)) {
        i2_up = now_up;
        i2_down = now_down;
        idx2 = i;
      }
    }

    BigInt leq(sum);
    leq.mult(i1_down);
    leq.mult(i2_down);

    BigInt req = i1_up;
    req.mult(i2_down);
    BigInt req2 = i2_up;
    req2.mult(i1_down);
    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: 0 / 22
• Subtask 3: 0 / 28
• Subtask 4: 0 / 39