Submission #956605

#	Time	Username	Problem	Language	Result	Execution time	Memory
956605		xetrk	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	448 KiB

shortcut

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

#pragma warning(disable:4996)

typedef long long ll;
typedef long double ld;

ll pos[1000100] = {0};

ll leftPos, rightPos;

bool CanShortcut(ll shortLen, int n, std::vector<int> d, int c)
{
	int leftConnectIdx, rightConnectIdx;
	// 맨 왼쪽에서 shortLen으로 갈수있는 최대인 곳
	for (rightConnectIdx = 0; rightConnectIdx < n; rightConnectIdx++)
	{
		if (pos[rightConnectIdx] + d[rightConnectIdx] - leftPos > shortLen)
			break;
	}
	if (rightConnectIdx >= n) rightConnectIdx = n - 1;
	for (leftConnectIdx = n - 1; leftConnectIdx >= 0; leftConnectIdx--)
	{
		if (rightPos - (pos[leftConnectIdx] - d[leftConnectIdx]) > shortLen)
			break;
	}
	if (leftConnectIdx < 0) leftConnectIdx = 0;

	if (leftConnectIdx >= rightConnectIdx)
		return false;

	//leftPos-> leftConnect->rightConnect->rightPos

	ll newMaxLen = (pos[leftConnectIdx] - leftPos) + c + (rightPos - pos[rightConnectIdx]);
	
	return newMaxLen <= shortLen;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	//n--;
	leftPos = rightPos = 0;
	for (int i = 0; i < n; i++)
	{
		if (i < n - 1) pos[i + 1] = pos[i] + l[i];
		leftPos = min(leftPos, pos[i] - d[i]);
		rightPos = max(rightPos, pos[i] + d[i]);
	}

	ll s = 1, e = rightPos*2, mid;
	while (s + 1 < e)
	{
		mid = (s + e) / 2;

		// mid는 가능
		if (CanShortcut(mid, n, d, c))
			e = mid;
		//mid는 불가능
		else
			s = mid + 1;
			 
	}
	return min(rightPos - leftPos, e);
}

Compilation message (stderr)

shortcut.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning(disable:4996)
      |

• 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