Submission #14194

#	Time	Username	Problem	Language	Result	Execution time	Memory
14194		ainu7	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	902 ms	9156 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>
#include <sys/time.h>
using namespace std;

double getTime()
{
  timeval tv;
  gettimeofday(&tv, 0);
  return (tv.tv_sec + tv.tv_usec * 0.000001);
}


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=1; i<max_radix; i++)
      if (digit[i]) mmax = i;
    for (int i=1; i<max_radix; i++)
      if (a.digit[i]) a_mmax = i;

    for (int i=0; i<=mmax; i++) {
      if (!digit[i]) continue;
      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=0; i<max_radix; i++) {
      digit[i] *= a;
    }
    for (int i=0; i<max_radix-1; i++) {
      if (digit[i] >= mod) { digit[i+1] += digit[i] / mod; digit[i] %= mod; }
    }
  }

  void add(BigInt a) {
    for (int i=0; i<max_radix; 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 digit[i] > a.digit[i];
    }

    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()
{
  double tm1 = getTime();

  srand(time(0));
  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];
  }

  vector<int> order(N);
  for (int i=0; i<N; i++) order[i] = i;
  for (int i=0; i<N; i++) {
    int j = rand()%(N-i) + i;
    swap(order[i], order[j]);
    swap(H[i], H[j]);
    swap(T[i], T[j]);
  }
  for (int i=0; i<N; 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 ++) {
    if (getTime() - tm1 > 0.9) break;
//    printf("%d\n", iter);
    BigInt mid = ll;
    mid.add(rr);
    ll.mult(2);
    rr.mult(2);
    down.mult(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 = down;
      now_up.mult(HT[i]);
      now_up.add(mid);
    
      if (idx2 == -1 || is_bigger(now_up, T[i], i2_up, T[idx2])) {
        if (idx1 == -1 || is_bigger(now_up, T[i], i1_up, T[idx1])) {
          i2_up = i1_up;
          i1_up = now_up;
          idx2 = idx1;
          idx1 = i;
        } else {
          i2_up = now_up;
          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;
  }

  int r1 = order[idx1];
  int r2 = order[idx2];
  if (r1 > r2) swap(r1, r2);
  cout << r1 + 1 << " " << r2 + 1 << endl;
}

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