oj.uz

Submission #956600

# Submission time Handle Problem Language Result Execution time Memory
956600 2024-04-02T08:16:54 Z xetrk Shortcut (IOI16_shortcut) C++14
0 / 100
 0 ms 348 KB 
#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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 4 vs contestant 3
5 Halted 0 ms 0 KB -