QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224942#7617. Spectaclemendicillin2#Compile Error//C++173.4kb2023-10-23 18:09:252023-10-23 18:09:27

Judging History

你现在查看的是最新测评结果

  • [2023-10-23 18:09:27]
  • 评测
  • [2023-10-23 18:09:25]
  • 提交

answer

hello
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

template <class T> void setmax(T& a, const T& b) {
	if (a < b) a = b;
}
template <class T> void setmin(T& a, const T& b) {
	if (a > b) a = b;
}

template <class T> ostream& operator << (ostream& os, const vector<T>& A) {
	assert(!A.empty());
	int N = int(A.size());
	for (int i = 0; i < N; i++) {
		os << A[i];
		if (i+1 < N) {
			os << ' ';
		}
	}
	return os;
}

const ll INF = 1.01e18;
template <class T>
vector<T> convolution(const vector<T>& A, const vector<T>& B) {
	const int N = int(A.size());
	const int M = int(B.size());
	const int L = N+M-1;
	vector<T> C(L, +INF);
	{
		int cur = 0;
		int j = -1;
		for (int i = 0; i < N; i++) {
			if (A[i] == +INF) break;
			while (j+1 < M && B[j+1] <= A[i]) {
				j++;
			}
			if (j >= 0) {
				while (cur <= i+j) {
					setmin(C[cur++], A[i]);
				}
			}
		}
	}
	{
		int cur = 0;
		int j = -1;
		for (int i = 0; i < M; i++) {
			if (B[i] == +INF) break;
			while (j+1 < N && A[j+1] <= B[i]) {
				j++;
			}
			if (j >= 0) {
				while (cur <= i+j) {
					setmin(C[cur++], B[i]);
				}
			}
		}
	}
	cerr << "A = " << A << endl;
	cerr << "B = " << B << endl;
	cerr << "C = " << C << endl;
	return C;
}

struct dp_t : array<array<vector<ll>, 2>, 2> {
	dp_t() {}
	dp_t(ll x) {
		(*this)[0][0] = {0, +INF};
		(*this)[0][1] = {+INF, +INF};
		(*this)[1][0] = {+INF, +INF};
		(*this)[1][1] = {+INF, x};
	}

	friend dp_t merge(const dp_t& l, const dp_t& r) {
		dp_t res;
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				auto f00 = convolution(l[a][0], r[0][b]);
				auto f01 = convolution(l[a][0], r[1][b]);
				auto f10 = convolution(l[a][1], r[0][b]);
				const int L = int(f00.size());
				res[a][b].resize(L);
				for (int i = 0; i < L; i++) {
					res[a][b][i] = min({f00[i], f01[i], f10[i]});
				}
			}
		}
		while (true) {
			ll v = min({res[0][0].back(), res[0][1].back(),
				res[1][0].back(), res[1][1].back()});
			if (v == +INF) {
				res[0][0].pop_back();
				res[0][1].pop_back();
				res[1][0].pop_back();
				res[1][1].pop_back();
			} else {
				break;
			}
		}
		return res;
	}
};

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N; cin >> N;
	vector<ll> A(N);
	for (ll& a : A) cin >> a;
	sort(A.begin(), A.end());

	N--;
	vector<dp_t> stuff(N);
	for (int i = 0; i < N; i++) {
		stuff[i] = dp_t(A[i+1] - A[i]);
		cerr << A[i+1] - A[i] << " \n"[i+1==N];
	}

	auto res = yc([&](auto self, int l, int r) -> dp_t {
		if (l+1 == r) {
			return stuff[l];
		} else {
			int m = (l+r)/2;
			return merge(self(l, m), self(m, r));
		}
	})(0, N);
	for (int n = 1; n <= (N+1)/2; n++) {
		ll v = +INF;
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				if (int(res[a][b].size()) > n) {
					setmin(v, res[a][b][n]);
				}
			}
		}
		cout << v << '\n';
	}

	return 0;
}

Details

answer.code:1:1: error: ‘hello’ does not name a type
    1 | hello
      | ^~~~~