oj.uz

Submission #14193

# Submission time Handle Problem Language Result Execution time Memory
14193 2015-05-03T12:41:43 Z ainu7 볼질 (OJUZ10_ballparade) C++
0 / 100
 729 ms 8568 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
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7980 KB Output isn't correct
2 Incorrect 721 ms 8568 KB Output isn't correct
3 Incorrect 0 ms 7980 KB Output isn't correct
4 Incorrect 68 ms 7980 KB Output isn't correct
5 Incorrect 0 ms 7980 KB Output isn't correct
6 Incorrect 364 ms 8176 KB Output isn't correct
7 Incorrect 0 ms 7980 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 723 ms 8568 KB Output isn't correct
2 Incorrect 1 ms 7980 KB Output isn't correct
3 Incorrect 72 ms 7980 KB Output isn't correct
4 Incorrect 358 ms 8176 KB Output isn't correct
5 Incorrect 0 ms 7980 KB Output isn't correct
6 Incorrect 0 ms 7980 KB Output isn't correct
7 Incorrect 727 ms 8568 KB Output isn't correct
8 Incorrect 0 ms 7980 KB Output isn't correct

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 726 ms 8568 KB Output isn't correct
2 Incorrect 0 ms 7980 KB Output isn't correct
3 Incorrect 0 ms 7980 KB Output isn't correct
4 Incorrect 726 ms 8568 KB Output isn't correct
5 Incorrect 726 ms 8568 KB Output isn't correct
6 Incorrect 723 ms 8568 KB Output isn't correct
7 Incorrect 722 ms 8568 KB Output isn't correct
8 Incorrect 0 ms 7980 KB Output isn't correct
9 Incorrect 729 ms 8568 KB Output isn't correct
10 Incorrect 719 ms 8568 KB Output isn't correct
11 Incorrect 365 ms 8176 KB Output isn't correct
12 Incorrect 75 ms 7980 KB Output isn't correct
13 Incorrect 0 ms 7980 KB Output isn't correct
14 Incorrect 725 ms 8568 KB Output isn't correct
15 Incorrect 720 ms 8568 KB Output isn't correct