Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- mport java.io.*;
- import java.util.Locale;
- import java.util.Random;
- import java.util.StringTokenizer;
- public class F {
- String filename = "";//filename here, System.in/out if no file
- FastScanner in;
- PrintWriter out;
- int[] a;
- long[] a_copy;
- int n;
- int s;
- static long kth(long[] array, int l, int r, int k) {
- final Random random = new Random();
- int i = l;
- int j = r;
- long x = array[l + random.nextInt(r - l + 1)];
- while (i <= j) {
- while (array[i] < x) {
- i++;
- }
- while (array[j] > x) {
- j--;
- }
- if (i <= j) {
- long temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- i++;
- j--;
- }
- }
- if (l <= k && k <= j) {
- return kth(array, l, j, k);
- }
- if (i <= k && k <= r) {
- return kth(array, i, r, k);
- }
- return array[k];
- }
- long return_666(long rz) {
- for (int i = 0; i < a.length; i++) {
- a_copy[i] = a[i];
- }
- for (int i = 0; i < n; i++) {
- a_copy[i] = a_copy[i] - i * rz;
- }
- long s = kth(a_copy, 0, n - 1, n / 2);
- return s;
- }
- long f(long raz) {
- long sum = 0;
- for (int i = 0; i < a.length; i++) {
- a_copy[i] = a[i];
- }
- for (int i = 0; i < n; i++) {
- a_copy[i] = a_copy[i] - (long) i * (long) raz;
- }
- long s = kth(a_copy, 0, n - 1, n / 2);
- for (int i = 0; i < n; i++) {
- long a = sum;
- long cur = Math.abs(a_copy[i] - s);
- sum += cur;
- if (sum - cur != a || sum - a != cur) {
- return Long.MAX_VALUE;
- }
- }
- return sum;
- }
- void solve() {
- //your code here
- n = in.nextInt();
- a = new int[n];
- a_copy = new long[n];
- for (int i = 0; i < n; i++) {
- a[i] = in.nextInt();
- a_copy[i] = a[i];
- }
- int d = 0;
- s = 0;
- long l = -1000 * 1000 * 1000;
- long r = 1000 * 1000 * 1000;
- if (n <= 10000) {
- l = -2 * 1000 * 1000 * 1000 - 7;
- r = 2 * 1000 * 1000 * 1000 + 7;
- } else {
- if (n <= 100 * 1000) {
- l = -1000 * 10000 - 7;
- r = 1000 * 10000 + 1;
- } else {
- l = -100 * 1000;
- r = 100 * 1000;
- }
- }
- while (r - l > 1) {
- long m = (l + r) / 2;
- if (f(m + 1) < f(m)) {
- l = m;
- } else {
- r = m;
- }
- }
- out.print(return_666(l + 1) + " " + (l + 1));
- }
- void run() throws IOException {
- InputStream input = System.in;
- OutputStream output = System.out;
- /* try {
- File f = new File(filename + ".in");
- if (f.exists() && f.canRead()) {
- input = new FileInputStream(f);
- output = new FileOutputStream(filename + ".out");
- }
- } catch (IOException e) {
- }*/
- in = new FastScanner(input);
- out = new PrintWriter(new BufferedOutputStream(output));
- solve();
- in.close();
- out.close();
- }
- public static void main(String[] args) throws IOException {
- Locale.setDefault(Locale.US);
- new F().run();
- }
- class FastScanner implements Closeable {
- private BufferedReader br;
- private StringTokenizer tokenizer;
- public FastScanner(InputStream stream) throws FileNotFoundException {
- br = new BufferedReader(new InputStreamReader(stream));
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return
- tokenizer.nextToken();
- }
- public String nextLine() {
- if (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- return br.readLine();
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken("\n");
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public double nextDouble() {
- return
- Double.parseDouble(next());
- }
- @Override
- public void close() throws IOException {
- br.close();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement