oj.uz

답안 #20616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20616 2017-02-12T16:39:30 Z model_code Aliens (IOI16_aliens) C
4 / 100
 0 ms 34876 KB 
// name = aliens_c.c, type = c.gcc

#include "aliens_c.h"
#include <assert.h>
#include <stdlib.h>

#define min(x, y) (x) > (y) ? (y) : (x)
#define max(x, y) (x) < (y) ? (y) : (x)

#define N 1234567

typedef struct {
  int start;
  int end;
} range;

range ranges[N];
long long as[N], bs[N];
int fs[N];
int size, opt;

int comp(void const *a_, void const *b_) {
  range *a = (range *)a_;
  range *b = (range *)b_;
  if (a->start != b->start) return a->start - b->start;
  return b->end - a->end;
}

void clear_cht() {
  size = opt = 0;
}

double intersection(long long a1, long long b1, long long a2, long long b2) {
  return 1.0 * (double) (b2 - b1) / (double) (a1 - a2);
}

int get_max(long v) {
  opt = min(opt, size - 1);
  while (opt + 1 < size) {
    double x = intersection(as[opt], bs[opt], as[opt + 1], bs[opt + 1]);
    if (v > x) {
      opt++;
    } else {
      break;
    }
  }
  return opt;
}

void add_line(long long a, long long b, int bomb) {
  while (size > 1) {
    double x1 = intersection(as[size - 2], bs[size - 2], as[size - 1], bs[size - 1]);
    double x2 = intersection(as[size - 1], bs[size - 1], a, b);
    if (x1 < x2) {
      break;
    } else {
      size--;
    }
  }
  as[size] = a;
  bs[size] = b;
  fs[size] = bomb;
  size++;
}

long long sqr(long long x) {
  return x * x;
}

void getValue(int n, long long c, long long *value_res, long long *bombs_res) {
  clear_cht();
  add_line(-2 * (ranges[0].start - 1), sqr(ranges[0].start - 1), 0);
  for (int i = 1; i <= n; i++) {
    int line = get_max(ranges[i - 1].end);
    long long value = as[line] * ranges[i - 1].end + bs[line] + sqr(ranges[i - 1].end) + c;
    int bombs = fs[line] + 1;
    if (i < n) {
      add_line(-2 * (ranges[i].start - 1), value + sqr(ranges[i].start - 1) - sqr(max(0, ranges[i - 1].end - ranges[i].start + 1)), bombs);
    } else {
      *value_res = value;
      *bombs_res = bombs;
      return;
    }
  }
  assert(0);
}

long long take_photos(int n, int m, int k, int *x, int *y) {
  for (int i = 0; i < n; i++) {
    ranges[i] = (range) {min(x[i], y[i]), max(x[i], y[i])};
  }
  qsort(ranges, n, sizeof(range), comp);
  int maxRight = -1;
  int cn = 0;
  for (int i = 0; i < n; i++) {
    if (ranges[i].end > maxRight) {
      maxRight = ranges[i].end;
      ranges[cn++] = ranges[i];
    }
  }
  n = cn;
  k = min(k, n);
  clear_cht();
  long long left = 0;
  long long right = 1LL * m * m + 1;
  if (right % 2 != 0) {
    ++right;
  }
  while (left < right - 1) {
    long long mid = (left + right) >> 1;
    long long c = mid + 1;
    long long value, bombs;
    getValue(n, c, &value, &bombs);
    if (bombs < k) {
      right = mid;
    } else {
      left = mid;
    }
  }
  long long value1, bombs1, value2, bombs2;
  getValue(n, left + 1, &value1, &bombs1);
  getValue(n, right + 1, &value2, &bombs2);
  long long answer1 = value1 - bombs1 * (left + 1);
  long long answer2 = value2 - bombs2 * (right + 1);
  if (bombs1 == k) {
    return answer1;
  } else if (bombs2 == k) {
    return answer2;
  } else {
    long long diff = answer1 - answer2;
    return answer1 + diff / (bombs1 - bombs2) * (k - bombs1);
  }
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 4
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 4
4 Correct 0 ms 34876 KB Correct answer: answer = 12
5 Correct 0 ms 34876 KB Correct answer: answer = 52
6 Correct 0 ms 34876 KB Correct answer: answer = 210
7 Correct 0 ms 34876 KB Correct answer: answer = 88
8 Correct 0 ms 34876 KB Correct answer: answer = 7696
9 Correct 0 ms 34876 KB Correct answer: answer = 1
10 Correct 0 ms 34876 KB Correct answer: answer = 2374
11 Correct 0 ms 34876 KB Correct answer: answer = 9502
12 Correct 0 ms 34876 KB Correct answer: answer = 49
13 Correct 0 ms 34876 KB Correct answer: answer = 151
14 Correct 0 ms 34876 KB Correct answer: answer = 7550
15 Correct 0 ms 34876 KB Correct answer: answer = 7220
16 Correct 0 ms 34876 KB Correct answer: answer = 7550
17 Correct 0 ms 34876 KB Correct answer: answer = 10000
18 Correct 0 ms 34876 KB Correct answer: answer = 10000
19 Correct 0 ms 34876 KB Correct answer: answer = 624
20 Correct 0 ms 34876 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 1
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 1
4 Correct 0 ms 34876 KB Correct answer: answer = 5
5 Correct 0 ms 34876 KB Correct answer: answer = 41
6 Correct 0 ms 34876 KB Correct answer: answer = 71923
7 Runtime error 0 ms 34876 KB Execution killed because of forbidden syscall sysinfo (99)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 4
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 4
4 Correct 0 ms 34876 KB Correct answer: answer = 12
5 Correct 0 ms 34876 KB Correct answer: answer = 52
6 Correct 0 ms 34876 KB Correct answer: answer = 210
7 Correct 0 ms 34876 KB Correct answer: answer = 88
8 Correct 0 ms 34876 KB Correct answer: answer = 7696
9 Correct 0 ms 34876 KB Correct answer: answer = 1
10 Correct 0 ms 34876 KB Correct answer: answer = 2374
11 Correct 0 ms 34876 KB Correct answer: answer = 9502
12 Correct 0 ms 34876 KB Correct answer: answer = 49
13 Correct 0 ms 34876 KB Correct answer: answer = 151
14 Correct 0 ms 34876 KB Correct answer: answer = 7550
15 Correct 0 ms 34876 KB Correct answer: answer = 7220
16 Correct 0 ms 34876 KB Correct answer: answer = 7550
17 Correct 0 ms 34876 KB Correct answer: answer = 10000
18 Correct 0 ms 34876 KB Correct answer: answer = 10000
19 Correct 0 ms 34876 KB Correct answer: answer = 624
20 Correct 0 ms 34876 KB Correct answer: answer = 10000
21 Correct 0 ms 34876 KB Correct answer: answer = 1
22 Correct 0 ms 34876 KB Correct answer: answer = 4
23 Correct 0 ms 34876 KB Correct answer: answer = 1
24 Correct 0 ms 34876 KB Correct answer: answer = 5
25 Correct 0 ms 34876 KB Correct answer: answer = 41
26 Correct 0 ms 34876 KB Correct answer: answer = 71923
27 Runtime error 0 ms 34876 KB Execution killed because of forbidden syscall sysinfo (99)
28 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 4
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 4
4 Correct 0 ms 34876 KB Correct answer: answer = 12
5 Correct 0 ms 34876 KB Correct answer: answer = 52
6 Correct 0 ms 34876 KB Correct answer: answer = 210
7 Correct 0 ms 34876 KB Correct answer: answer = 88
8 Correct 0 ms 34876 KB Correct answer: answer = 7696
9 Correct 0 ms 34876 KB Correct answer: answer = 1
10 Correct 0 ms 34876 KB Correct answer: answer = 2374
11 Correct 0 ms 34876 KB Correct answer: answer = 9502
12 Correct 0 ms 34876 KB Correct answer: answer = 49
13 Correct 0 ms 34876 KB Correct answer: answer = 151
14 Correct 0 ms 34876 KB Correct answer: answer = 7550
15 Correct 0 ms 34876 KB Correct answer: answer = 7220
16 Correct 0 ms 34876 KB Correct answer: answer = 7550
17 Correct 0 ms 34876 KB Correct answer: answer = 10000
18 Correct 0 ms 34876 KB Correct answer: answer = 10000
19 Correct 0 ms 34876 KB Correct answer: answer = 624
20 Correct 0 ms 34876 KB Correct answer: answer = 10000
21 Correct 0 ms 34876 KB Correct answer: answer = 1
22 Correct 0 ms 34876 KB Correct answer: answer = 4
23 Correct 0 ms 34876 KB Correct answer: answer = 1
24 Correct 0 ms 34876 KB Correct answer: answer = 5
25 Correct 0 ms 34876 KB Correct answer: answer = 41
26 Correct 0 ms 34876 KB Correct answer: answer = 71923
27 Runtime error 0 ms 34876 KB Execution killed because of forbidden syscall sysinfo (99)
28 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 4
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 4
4 Correct 0 ms 34876 KB Correct answer: answer = 12
5 Correct 0 ms 34876 KB Correct answer: answer = 52
6 Correct 0 ms 34876 KB Correct answer: answer = 210
7 Correct 0 ms 34876 KB Correct answer: answer = 88
8 Correct 0 ms 34876 KB Correct answer: answer = 7696
9 Correct 0 ms 34876 KB Correct answer: answer = 1
10 Correct 0 ms 34876 KB Correct answer: answer = 2374
11 Correct 0 ms 34876 KB Correct answer: answer = 9502
12 Correct 0 ms 34876 KB Correct answer: answer = 49
13 Correct 0 ms 34876 KB Correct answer: answer = 151
14 Correct 0 ms 34876 KB Correct answer: answer = 7550
15 Correct 0 ms 34876 KB Correct answer: answer = 7220
16 Correct 0 ms 34876 KB Correct answer: answer = 7550
17 Correct 0 ms 34876 KB Correct answer: answer = 10000
18 Correct 0 ms 34876 KB Correct answer: answer = 10000
19 Correct 0 ms 34876 KB Correct answer: answer = 624
20 Correct 0 ms 34876 KB Correct answer: answer = 10000
21 Correct 0 ms 34876 KB Correct answer: answer = 1
22 Correct 0 ms 34876 KB Correct answer: answer = 4
23 Correct 0 ms 34876 KB Correct answer: answer = 1
24 Correct 0 ms 34876 KB Correct answer: answer = 5
25 Correct 0 ms 34876 KB Correct answer: answer = 41
26 Correct 0 ms 34876 KB Correct answer: answer = 71923
27 Runtime error 0 ms 34876 KB Execution killed because of forbidden syscall sysinfo (99)
28 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34876 KB Correct answer: answer = 4
2 Correct 0 ms 34876 KB Correct answer: answer = 4
3 Correct 0 ms 34876 KB Correct answer: answer = 4
4 Correct 0 ms 34876 KB Correct answer: answer = 12
5 Correct 0 ms 34876 KB Correct answer: answer = 52
6 Correct 0 ms 34876 KB Correct answer: answer = 210
7 Correct 0 ms 34876 KB Correct answer: answer = 88
8 Correct 0 ms 34876 KB Correct answer: answer = 7696
9 Correct 0 ms 34876 KB Correct answer: answer = 1
10 Correct 0 ms 34876 KB Correct answer: answer = 2374
11 Correct 0 ms 34876 KB Correct answer: answer = 9502
12 Correct 0 ms 34876 KB Correct answer: answer = 49
13 Correct 0 ms 34876 KB Correct answer: answer = 151
14 Correct 0 ms 34876 KB Correct answer: answer = 7550
15 Correct 0 ms 34876 KB Correct answer: answer = 7220
16 Correct 0 ms 34876 KB Correct answer: answer = 7550
17 Correct 0 ms 34876 KB Correct answer: answer = 10000
18 Correct 0 ms 34876 KB Correct answer: answer = 10000
19 Correct 0 ms 34876 KB Correct answer: answer = 624
20 Correct 0 ms 34876 KB Correct answer: answer = 10000
21 Correct 0 ms 34876 KB Correct answer: answer = 1
22 Correct 0 ms 34876 KB Correct answer: answer = 4
23 Correct 0 ms 34876 KB Correct answer: answer = 1
24 Correct 0 ms 34876 KB Correct answer: answer = 5
25 Correct 0 ms 34876 KB Correct answer: answer = 41
26 Correct 0 ms 34876 KB Correct answer: answer = 71923
27 Runtime error 0 ms 34876 KB Execution killed because of forbidden syscall sysinfo (99)
28 Halted 0 ms 0 KB -