Submission #1085609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085609		I_am_Polish_Girl	Maze (JOI23_ho_t3)	C++14	51 / 100	2072 ms	1454024 KiB

Main

#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;


typedef long long ll;
typedef long double ld;

int log_ = 21;
int inf = 1000000007;

long long mod = 998244353;

int p = 499;

int NADIYA = 39;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	int i_st, j_st;
	cin >> i_st >> j_st;

	i_st--;
	j_st--;

	int i_f, j_f;
	cin >> i_f >> j_f;

	i_f--;
	j_f--;


	vector <int> deep;
	
	
	vector <string> vs(n);
	for (int i = 0; i < n; i++)
		cin >> vs[i];
	

	int X = 2;
	int c = 1;

	int sz = 0;

	int K = 2 * k - 1;

	
	while (c * X <= K)
	{
		c *= X;
		sz++;
	}

	sz++;

	vector <vector <vector<int>>> bin(n);

	vector <vector <int>> g(n*m*(2*sz));


	for (int i = 0; i < n; i++)
	{
		bin[i].resize(m);
		for (int j = 0; j < m; j++)
		{
			bin[i][j].resize(sz);
		}
	}

	int f = 0;

	vector <pair <int, int>> vp(n * m);


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			bin[i][j][0] = f;
			
			vp[f] = { i , j };

			f++;
		}
	}

	int f2 = f;

	int y = 1;
	for (int k_ = 1; k_ < sz; k_ ++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				bin[i][j][k_] = f;
				
				g[f].resize(X);

				for (int x = 0; x < X; x++)
				{
					g[f][x] = bin[i][min(j + y * x, m - 1)][k_ - 1];
				}
				
				f++;
			}
		}

		y *= X;
	}


	y /= X;



	vector <vector <vector<int>>> bin2(n);


	for (int i = 0; i < n; i++)
	{
		bin2[i].resize(m);
		for (int j = 0; j < m; j++)
		{
			bin2[i][j].resize(sz);
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			bin2[i][j][0] = bin[i][j][0];
		}
	}

	y = 1;
	for (int k_ = 1; k_ < sz; k_++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				bin2[i][j][k_] = f;

				g[f].resize(X);

				for (int x = 0; x < X; x++)
				{
					g[f][x] = bin2[min(i + y * x, n - 1)][j][k_ - 1];
				}

				f++;
			}
		}

		y *= X;
	}

	y /= X;






	deep.resize(g.size() ,inf);

	vector <vector < int>> q(2);

	for (int i = 0; i < 2; i++)
		q[i].resize(f);

	int f1_ = 0;
	int f2_ = 0;

	q[0][0] = bin[i_st][j_st][0];

	f1_ = 1;
	
	deep[bin[i_st][j_st][0]] = 0;

	vector <pair <int, int>> go;

	go.push_back({ 1 , 0 });
	go.push_back({ -1 , 0 });
	go.push_back({ 0 , 1 });
	go.push_back({ 0 , -1 });

	int d2 = -1;
	for (int d = 0 ; d < n*m+1  ; d ^= 1)
	{
		d2++;

		if (f1_ == 0)
			break;

		for (int ind = 0; ind < f1_; ind++)
		{
			int ind__ = q[d][ind];

			if (ind__ < f2)
			{
				int i_ = vp[ind__].first;
				int j_ = vp[ind__].second;

				for (int i = 0; i < 4; i++)
				{
					int i__ = i_ + go[i].first;
					int j__ = j_ + go[i].second;

					if ((i__ >= 0) and (i__ < n))
					{
						if ((j__ >= 0) and (j__ < m))
						{
							if (deep[bin[i__][j__][0]] > d2)
							{
								if (vs[i__][j__] == '.')
								{
									deep[bin[i__][j__][0]] = d2;

									q[d][f1_] = bin[i__][j__][0];
									f1_++;
								}
							}
						}
					}
				}
			}
			else
			{
				for (int i = 0; i < g[ind__].size(); i++)
				{
					int ind_s = g[ind__][i];

					if (deep[ind_s] > d2)
					{	
						deep[ind_s] = d2;
						
						q[d][f1_] = ind_s;
						f1_++;
					}
				}
			}
		}



		for (int ind = 0; ind < f1_; ind++)
		{
			int ind__ = q[d][ind];

			if (ind__ < f2)
			{
				int i_ = vp[ind__].first;
				int j_ = vp[ind__].second;


				if (i_ >= k) 
				{
					int l = j_ - (k - 1);
					int r = j_ + (k - 1);

					l = max(l, 0);
					r = min(r, m - 1);

					int i__ = i_ - k;
					int j__ = l;

					int lenth = r - l + 1;

					int c = 0;
					int x = 1;

					while (x * X <= lenth)
					{
						x *= X;
						c++;
					}

					for (int c_ = 0; c_ < (lenth / x); c_++)
					{
						if (deep[bin[i__][j__ + (c_ * x)][c]] == inf)
						{
							deep[bin[i__][j__ + (c_ * x)][c]] = d2 + 1;

							q[d ^ 1][f2_] = bin[i__][j__ + (c_ * x)][c];
							f2_++;
							//q[d + 1].push_back(bin[i__][j__ + (c_ * x)][c]);
						}
					}

					if (deep[bin[i__][r - x + 1][c]] == inf)
					{
						deep[bin[i__][r - x + 1][c]] = d2 + 1;
						
						q[d ^ 1][f2_] = bin[i__][r - x + 1][c];
						f2_++;

						//q[d + 1].push_back(bin[i__][r - x + 1][c]);
					}
					//q[d + 1].push_back(bin[i__][r - x+1][c]);
				}

				if (i_+ k < n) 
				{
					int l = j_ - (k - 1);
					int r = j_ + (k - 1);

					l = max(l, 0);
					r = min(r, m - 1);

					int i__ = i_ + k;
					int j__ = l;

					int lenth = r - l + 1;

					int c = 0;
					int x = 1;

					while (x * X <= lenth)
					{
						x *= X;
						c++;
					}

					for (int c_ = 0; c_ < (lenth / x); c_++)
					{
						if (deep[bin[i__][j__ + (c_ * x)][c]] == inf)
						{
							deep[bin[i__][j__ + (c_ * x)][c]] = d2 + 1;

							q[d ^ 1][f2_] = bin[i__][j__ + (c_ * x)][c];
							f2_++;
							//q[d + 1].push_back(bin[i__][j__ + (c_ * x)][c]);
						}
					}

					if (deep[bin[i__][r - x + 1][c]] == inf)
					{
						deep[bin[i__][r - x + 1][c]] = d2 + 1;

						q[d ^ 1][f2_] = bin[i__][r - x + 1][c];
						f2_++;

						//q[d + 1].push_back(bin[i__][r - x + 1][c]);
					}
					//q[d + 1].push_back(bin[i__][r - x+1][c]);
				}
				




				if (j_ >= k)
				{
					int l = i_ - (k - 1);
					int r = i_ + (k - 1);

					l = max(l, 0);
					r = min(r, n - 1);

					int i__ = l;
					int j__ = j_ - k;

					int lenth = r - l + 1;

					int c = 0;
					int x = 1;

					while (x * X <= lenth)
					{
						x *= X;
						c++;
					}

					for (int c_ = 0; c_ < (lenth / x); c_++)
					{
						if (deep[bin2[i__ + (c_ * x)][j__][c]] > d2 + 1)
						{
							deep[bin2[i__ + (c_ * x)][j__][c]] = d2 + 1;
							//q[d + 1].push_back(bin2[i__ + (c_ * x)][j__][c]);

							q[d ^ 1][f2_] = bin2[i__ + (c_ * x)][j__][c];
							f2_++;
						}
					}


					if (deep[bin2[r - x + 1][j__][c]] == inf)
					{
						deep[bin2[r - x + 1][j__][c]] = d2 + 1;
						//q[d + 1].push_back(bin2[r - x + 1][j__][c]);

						q[d ^ 1][f2_] = bin2[r - x + 1][j__][c];
						f2_++;
					}

					//q[d + 1].push_back(bin[l - x+1][j__][c]);
				}


				if (j_+k < m)
				{
					int l = i_ - (k - 1);
					int r = i_ + (k - 1);

					l = max(l, 0);
					r = min(r, n - 1);

					int i__ = l;
					int j__ = j_ + k;

					int lenth = r - l + 1;

					int c = 0;
					int x = 1;

					while (x * X <= lenth)
					{
						x *= X;
						c++;
					}

					for (int c_ = 0; c_ < (lenth / x); c_++)
					{
						if (deep[bin2[i__ + (c_ * x)][j__][c]] > d2 + 1)
						{
							deep[bin2[i__ + (c_ * x)][j__][c]] = d2 + 1;
							//q[d + 1].push_back(bin2[i__ + (c_ * x)][j__][c]);

							q[d ^ 1][f2_] = bin2[i__ + (c_ * x)][j__][c];
							f2_++;
						}
					}


					if (deep[bin2[r - x + 1][j__][c]] > d2 + 1)
					{
						deep[bin2[r - x + 1][j__][c]] = d2 + 1;
						//q[d + 1].push_back(bin2[r - x + 1][j__][c]);

						q[d ^ 1][f2_] = bin2[r - x + 1][j__][c];
						f2_++;
					}

					//q[d + 1].push_back(bin[l - x+1][j__][c]);
				}


			}
		}

		for (int i = 0; i < f2_; i++)
		{
			q[d][i] = q[d ^ 1][i];
		}

		f1_ = f2_;
		f2_ = 0;
	}


	//cout << deep[i_f][j_f] << "\n";

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (abs(i - i_f) <= k)
			{
				if (abs(j - j_f) <= k)
				{
					if ((abs(i - i_f) + abs(j - j_f)) != 2 * k)
					{
						deep[bin[i_f][j_f][0]] = min(deep[bin[i_f][j_f][0]], deep[bin[i][j][0]] + 1);
					}
				}
			}
		}
	}

	cout << deep[bin[i_f][j_f][0]];
}

/*
5 5 2
2 2
4 4
#....
#.##.
####.
##...
.....
*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      | 
Main.cpp: In function 'int main()':
Main.cpp:256:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |     for (int i = 0; i < g[ind__].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6