oj.uz

Submission #14194

# Submission time Handle Problem Language Result Execution time Memory
14194 2015-05-03T12:42:14 Z ainu7 Be Two Bees (OJUZ10_b2b) C++
100 / 100
 902 ms 9156 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7980 KB Output is correct
2 Correct 0 ms 7980 KB Output is correct
3 Correct 2 ms 7980 KB Output is correct
4 Correct 0 ms 7980 KB Output is correct
5 Correct 0 ms 7980 KB Output is correct
6 Correct 0 ms 7980 KB Output is correct
7 Correct 0 ms 7980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7980 KB Output is correct
2 Correct 4 ms 7980 KB Output is correct
3 Correct 12 ms 7980 KB Output is correct
4 Correct 18 ms 7980 KB Output is correct
5 Correct 17 ms 7980 KB Output is correct
6 Correct 0 ms 7980 KB Output is correct
7 Correct 12 ms 7980 KB Output is correct
8 Correct 14 ms 7980 KB Output is correct
9 Correct 0 ms 7980 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 8664 KB Output is correct
2 Correct 894 ms 8808 KB Output is correct
3 Correct 900 ms 9156 KB Output is correct
4 Correct 877 ms 9156 KB Output is correct
5 Correct 901 ms 9156 KB Output is correct
6 Correct 887 ms 9156 KB Output is correct
7 Correct 900 ms 9156 KB Output is correct
8 Correct 498 ms 8376 KB Output is correct
9 Correct 901 ms 9156 KB Output is correct
10 Correct 893 ms 9156 KB Output is correct
11 Correct 713 ms 8556 KB Output is correct
12 Correct 902 ms 9156 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 9156 KB Output is correct
2 Correct 890 ms 9156 KB Output is correct
3 Correct 889 ms 9156 KB Output is correct
4 Correct 898 ms 8664 KB Output is correct
5 Correct 879 ms 9156 KB Output is correct
6 Correct 902 ms 9156 KB Output is correct
7 Correct 868 ms 9156 KB Output is correct
8 Correct 899 ms 9156 KB Output is correct
9 Correct 893 ms 9156 KB Output is correct
10 Correct 896 ms 9156 KB Output is correct
11 Correct 875 ms 9156 KB Output is correct
12 Correct 883 ms 8808 KB Output is correct
13 Correct 864 ms 9156 KB Output is correct
14 Correct 895 ms 9156 KB Output is correct
15 Correct 522 ms 8244 KB Output is correct
16 Correct 892 ms 9156 KB Output is correct
17 Correct 883 ms 8808 KB Output is correct