Submission #1254029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254029		jwvg0425	Obstacles for a Llama (IOI25_obstacles)	C++20	Compilation error	0 ms	0 KiB

obstacles

#include "obstacles.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> t, h;

void expand(int& l, int& r, int& minh, int v)
{
	while (l > 0 && h[l - 1] < v)
	{
		l--;
		minh = min(minh, h[l]);
	}

	while (r + 1 < h.size() && h[r + 1] < v)
	{
		r++;
		minh = min(minh, h[r]);
	}
}

bool bruteforce(int s, int d)
{

	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, -1, 0, 1 };

	set<ii> vis;

	queue<ii> q;

	q.emplace(s, 0);
	vis.emplace(s, 0);

	while (!q.empty())
	{
		ii now = q.front();
		q.pop();

		if (now == ii{ d, 0 })
			return true;

		for (int i = 0; i < 4; i++)
		{
			int nx = now.xx + dx[i];
			int ny = now.yy + dy[i];

			if (nx < 0 || nx >= h.size() || ny < 0 || ny >= t.size())
				continue;

			if (vis.find({ nx, ny }) != vis.end())
				continue;

			if (h[nx] >= t[ny])
				continue;

			vis.emplace(nx, ny);
			q.emplace(nx, ny);
		}
	}

	return false;
}

bool can_reach(int l, int r, int s, int d)
{
	int sl = s, sr = s;
	int mins = h[s];
	int dl = d, dr = d;
	int mind = h[d];
	
	for (int y = 0; y < t.size(); y++)
	{
		// 잠기면 끝
		if (mins >= t[y] || mind >= t[y])
			return false;

		// 아니면 가능한 한 확장
		expand(sl, sr, mins, t[y]);
		expand(dl, dr, mind, t[y]);

		// 확장한 구간이 겹치면 끝
		int l = max(sl, dl);
		int r = min(sr, dr);

		if (l <= r)
			return true;
	}

	return false;
}


void initialize(vector<int> T, vector<int> H)
{
	t = T;
	h = H;

	/*while (true)
	{
		for (auto& ti : t)
			ti = rand() % 10;

		for (auto& hi : h)
			hi = rand() % 10;

		for (int s = 0; s < H.size(); s++)
		{
			for (int d = 0; d < H.size(); d++)
			{
				if (h[s] >= t[0] || h[d] >= t[0])
					continue;

				bool output = can_reach(0, 0, s, d);
				bool expect = bruteforce(s, d);
				if (expect != output)
				{
					printf("ERR!!!\n");

					for (int i = 0; i < t.size(); i++)
						printf("%d ", t[i]);
					printf("\n");

					for (int i = 0; i < h.size(); i++)
						printf("%d ", h[i]);
					printf("\n");

					printf("%d %d\n", s, d);

					printf("expect : %d, output: %d\n", expect, output);
					exit(0);
				}
			}
		}
	}

}

Compilation message (stderr)

obstacles.cpp:124:9: error: unterminated comment
  124 |         /*while (true)
      |         ^
obstacles.cpp: In function 'void initialize(std::vector<int>, std::vector<int>)':
obstacles.cpp:122:15: error: expected '}' at end of input
  122 |         h = H;
      |               ^
obstacles.cpp:120:1: note: to match this '{'
  120 | {
      | ^