oj.uz

Submission #14188

# Submission time Handle Problem Language Result Execution time Memory
14188 2015-05-03T11:52:43 Z ainu7 Be Two Bees (OJUZ10_b2b) C++
0 / 100
 1000 ms 2508 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>
using namespace std;

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

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 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 < 50; 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(H[i]);
      now_up.mult(down);
      now_up.mult(T[i]);
      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, 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);
    leq.mult(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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1724 KB Output is correct
2 Correct 0 ms 1724 KB Output is correct
3 Correct 1 ms 1724 KB Output is correct
4 Incorrect 0 ms 1724 KB Output isn't correct
5 Correct 0 ms 1724 KB Output is correct
6 Correct 0 ms 1724 KB Output is correct
7 Correct 0 ms 1724 KB Output is correct

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1724 KB Output is correct
2 Correct 20 ms 1724 KB Output is correct
3 Correct 10 ms 1724 KB Output is correct
4 Correct 20 ms 1724 KB Output is correct
5 Correct 20 ms 1724 KB Output is correct
6 Correct 20 ms 1724 KB Output is correct
7 Incorrect 0 ms 1724 KB Output isn't correct
8 Correct 19 ms 1724 KB Output is correct
9 Correct 20 ms 1724 KB Output is correct

Subtask #3
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2508 KB Program timed out
2 Correct 661 ms 1988 KB Output is correct
3 Execution timed out 1000 ms 2508 KB Program timed out
4 Execution timed out 1000 ms 2508 KB Program timed out
5 Execution timed out 1000 ms 2180 KB Program timed out
6 Execution timed out 1000 ms 2276 KB Program timed out
7 Correct 954 ms 2108 KB Output is correct
8 Execution timed out 1000 ms 2508 KB Program timed out
9 Execution timed out 1000 ms 2508 KB Program timed out
10 Execution timed out 1000 ms 2508 KB Program timed out
11 Execution timed out 1000 ms 2508 KB Program timed out
12 Execution timed out 1000 ms 2508 KB Program timed out

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2508 KB Program timed out
2 Execution timed out 1000 ms 2504 KB Program timed out
3 Execution timed out 1000 ms 2504 KB Program timed out
4 Execution timed out 1000 ms 2508 KB Program timed out
5 Execution timed out 1000 ms 2508 KB Program timed out
6 Execution timed out 1000 ms 2180 KB Program timed out
7 Execution timed out 1000 ms 2508 KB Program timed out
8 Execution timed out 1000 ms 2508 KB Program timed out
9 Execution timed out 1000 ms 2508 KB Program timed out
10 Execution timed out 1000 ms 2276 KB Program timed out
11 Correct 650 ms 1856 KB Output is correct
12 Execution timed out 1000 ms 2276 KB Program timed out
13 Execution timed out 1000 ms 2508 KB Program timed out
14 Execution timed out 1000 ms 2508 KB Program timed out
15 Execution timed out 1000 ms 2508 KB Program timed out
16 Execution timed out 1000 ms 2508 KB Program timed out
17 Execution timed out 1000 ms 2508 KB Program timed out