Submission #1088746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088746		alexz1205	Aliens (IOI16_aliens)	C++14	4 / 100	7 ms	520 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long int lint;
typedef __int128 llint;
typedef long double ldoub;

const int N = 1e5;
const llint PREC = 1e12;

array<llint, 2> ransDat[N];
vector<array<llint, 2>> rans;

llint dp[N+1];
int dp2[N+1];

int n, m;

void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

llint slope(llint sl1p1, llint sl1p2, llint sl2p1, llint sl2p2){
	for (int x = 0; x < 200; x ++){
		llint k1 = sl1p1 / sl1p2;
		llint k2 = sl2p1 / sl2p2;
		if (k1 != k2){
			return k1 - k2;
		}
		sl1p1 %= sl1p2;
		sl2p1 %= sl2p2;
		sl1p1 <<= 1;
		sl2p1 <<= 1;
	}
	return 0;
}

void calc(llint adjust){
	deque<array<llint, 3>> hull;
	hull.push_back({rans[0][0], -rans[0][0] * rans[0][0], 0});
	for (int x = 0; x < rans.size(); x ++){
		llint s = -2 * rans[x][1];
		llint B = rans[x][1] * rans[x][1];
		int a = 1, b = hull.size()-1;
		while (a <= b){
			int mid = (b-a+1)/2 + a;
			llint slp1 = (hull[mid][1] - hull[mid-1][1]);
			llint slp2 = (hull[mid][0] - hull[mid-1][0]);
			if (slope(slp1, slp2, s, (llint)1) < 0){
				b = mid-1;
			}else {
				a = mid+1;
			}
		}
		int r = a-1;

		dp[x] = -hull[r][1] + B + hull[r][0] * s + adjust;
		dp2[x] = hull[r][2] + 1;
		/*
		print(dp[x]);
		cout << " " << dp2[x] << endl;
		*/

		if (x == rans.size()-1) continue;

		llint right = min(rans[x][1], rans[x+1][0]);
		array<llint, 3> p = {rans[x+1][0], -dp[x] + (rans[x][1] - right) * (rans[x][1] - right) - rans[x+1][0] * rans[x+1][0], dp2[x]};

		while (hull.size() > 1){
			llint sl1p1 = (p[1] - hull[hull.size()-2][1]);
			llint sl1p2 = (p[0] - hull[hull.size()-2][0]);
			llint sl2p1 = (hull[hull.size()-1][1] - hull[hull.size()-2][1]);
			llint sl2p2 = (hull[hull.size()-1][0] - hull[hull.size()-2][0]);

			if (slope(sl1p1, sl1p2, sl2p1, sl2p2) >= 0){
				hull.pop_back();
			}else {
				break;
			}
		}
		hull.push_back(p);
	}
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	// dp_i = (pos_i-pos_j)**2 - (pos_right_j - pos_j)**2 + dp_j
	// (pos_right_j - pos_j) ** 2 - dp_j - pos_j ** 2 = pos_i ** 2 - dp_i - 2 * pos_i * pos_j
	// dp_i = (pos_i - pos_j + pos_right_j - pos_j) * (pos_i - pos_right_j) + dp_j
	// dp_i = pos_i ** 2 - 2 * pos_j * pos_i + 2 * pos_j * pos_right_j - pos_right_j ** 2 + dp_j
	// (pos_right_j ** 2 - 2 * pos_j * pos_right_j  - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_j * pos_i)
	//
	// subsume all within range
	// transition from possible left endpoints
	::n = n;
	::m = m;

	for (int x = 0; x < n; x ++){
		ransDat[x][0] = PREC*min(r[x], c[x]);
		ransDat[x][1] = PREC*(max(r[x], c[x]) + 1);
	}
	sort(ransDat, ransDat+n, [](array<llint, 2> a, array<llint, 2> b){return (a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]);});
	{
	llint ma = 0;
	for (int x = 0; x < n; x ++){
		if (ma >= ransDat[x][1]){
			continue;
		}
		ma = ransDat[x][1];
		rans.push_back(ransDat[x]);
	}
	}

	k = min(k, (int)rans.size());

	llint a = -(llint)1e12 * PREC * PREC, b = (llint)1e12 * PREC * PREC;
	llint best = 1e18 * (llint)1e18;
	while (a <= b){
		llint mid = (b-a+1)/2 + a;
		llint v = mid;
		calc(v);

		/*
		print(mid);
		cout << " ";
		print(dp[rans.size()-1]);
		cout << " " << dp2[rans.size()-1] << endl;;
		*/

		if (dp2[rans.size()-1] == k){
			llint val = dp[rans.size()-1];
			val -= k*v;
			val /= PREC;
			val /= PREC;
			return (lint)val;
		}
		if (dp2[rans.size()-1] < k){
			llint val = dp[rans.size()-1];
			val -= dp2[rans.size()-1]*v;
			val /= PREC;
			val /= PREC;
			best = min(best, val);
			b = mid-1;
		}else {
			a = mid+1;
		}
	}
	return best;
	//throw runtime_error("DID NOT FIND ANSWER\n");
	//exit(-1);
	//return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'void calc(llint)':
aliens.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<__int128, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int x = 0; x < rans.size(); x ++){
      |                  ~~^~~~~~~~~~~~~
aliens.cpp:70:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<__int128, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if (x == rans.size()-1) continue;
      |       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40