제출 #729407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729407		scanhex	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	212 KiB

shortcut

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include "shortcut.h"

using namespace std;
typedef long long nagai;

vector<vector<int>> stmin, stmax;
vector<int> mpow;

void initst(int n, vector<int> val)
{
	stmin.assign(20, vector<int>(n));
	stmax = stmin;
	mpow.resize(n);
	for (int i = 2; i <= n; ++i)
		mpow[i] = mpow[i >> 1] + 1;
	stmin[0] = stmax[0] = val;
	for (int i = 0; i < 19; ++i)
		for (int j = 0; j < n; ++j)
		{
			stmin[i + 1][j] = min(stmin[i][j], stmin[i][min(n - 1, j + (1 << i))]);
			stmax[i + 1][j] = max(stmax[i][j], stmax[i][min(n - 1, j + (1 << i))]);
		}
}

nagai qmin(int i, int j)
{
	int p = mpow[j - i];
	return min(stmin[p][i], stmin[p][j - (1 << p)]);
}

nagai qmax(int i, int j)
{
	int p = mpow[j - i];
	return max(stmax[p][i], stmax[p][j - (1 << p)]);
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d1, int c)
{
	vector<nagai> d(n);
	for (int i = 0; i < n; ++i)
		d[i] = d1[i];
	vector<nagai> pref(n);
	for (int i = 0; i < n - 1; ++i)
		pref[i + 1] = pref[i] + l[i];
	nagai mx = 0;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			mx = max(mx, pref[j] - pref[i] + d[i] + d[j]);
	int ib = 0, ie = n - 1;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (mx == pref[j] - pref[i] + d[i] + d[j])
				ib = max(ib, i), ie = min(ie, j);
	vector<nagai> prefd(n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < i; ++j)
			prefd[i] = max(prefd[i], pref[i] - pref[j] + d[j]);
	vector<nagai> suffd(n);
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			suffd[i] = max(suffd[i], pref[j] - pref[i] + d[j]);
	auto dist = [&](int i, int j, int a, int b)
	{
		if (b < a)
			return pref[b] - pref[i] + pref[j] - pref[a] + c;
		return pref[b] - pref[a];
	};
	auto check = [&](int i, int j)
	{
		int p2 = i;
		nagai curd = 0;
		nagai alldst = pref[j] - pref[i] + c;
		nagai diam1 = 0;
		for (int k = i; k <= j; ++k)
		{
			while (p2 < j && curd + l[p2] <= alldst - curd - l[p2])
				curd += l[p2++];
			if (p2 == j && curd + c <= alldst - curd - c)
				curd += c, p2 = i;
			while (p2 < j && curd + l[p2] <= alldst - curd - l[p2])
				curd += l[p2++];
			nagai nxtl = p2 == j ? c : l[p2];
			nagai nxtp2 = p2 == j ? i : p2 + 1;
			for (int l = i; l <= j; ++l)
				if (l < k)
					diam1 = max(diam1, min(pref[j] - pref[k] + pref[l] - pref[i] + d[k] + d[l] + c, pref[k] - pref[l] + d[k] + d[l]));
				else if (l > k)
					diam1 = max(diam1, min(pref[j] - pref[l] + pref[k] - pref[i] + d[k] + d[l] + c, pref[l] - pref[k] + d[k] + d[l]));
//			cout << k << ' ' << diam1 << endl;
//			for (int l = k; l != nxtp2; l = l == j ? i : l + 1)
//				diam1 = max(diam1, dist(i, j, k, l) + d[k] + d[l]);
//			for (int l = nxtp2; l != k; l = l == j ? i : l + 1)
//				diam1 = max(diam1, dist(i, j, l, k) + d[k] + d[l]);
//			cout << k << ' ' << diam1 << ' ' << p2 << endl;
			curd -= l[k];
		}
		nagai diam2 = 0;
		for (int k = i; k <= j; ++k)
		{
			diam2 = max(diam2, min(pref[j] - pref[k] + suffd[j] + d[k], c + pref[k] - pref[i] + d[k] + suffd[j]));
		}
		return make_pair(diam1, diam2);
	};
	nagai ans = mx;
	for (int i = 0; i < n; ++i)
	{
		int di1 = d[i];
		d[i] = max((nagai)d[i], prefd[i]);
		int L = i + 1, R = ie;
		while (R - L > 1)
		{
			int j = (L + R) / 2;
			auto p = check(i, j);
			nagai diam1 = p.first;
			nagai diam2 = p.second;
			if (diam1 < diam2)
				L = j;
			else
				R = j;
//			cout << i << ' ' << j << ' ' << diam << ' ' << ans << endl;
		}
		auto p = check(i, L);
//		cout << i << ' ' << L << ' ' << p.first << ' ' << p.second << endl;
		ans = min(ans, max(p.first, p.second));
		p = check(i, R);
//		cout << R << ' ' << p.first << ' ' << p.second << endl;
		ans = min(ans, max(p.first, p.second));
		d[i] = di1;
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In lambda function:
shortcut.cpp:86:10: warning: unused variable 'nxtl' [-Wunused-variable]
   86 |    nagai nxtl = p2 == j ? c : l[p2];
      |          ^~~~
shortcut.cpp:87:10: warning: unused variable 'nxtp2' [-Wunused-variable]
   87 |    nagai nxtp2 = p2 == j ? i : p2 + 1;
      |          ^~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:66:7: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
   66 |  auto dist = [&](int i, int j, int a, int b)
      |       ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3