結果

問題 No.2564 衝突予測
コンテスト
ユーザー ゆにぽけ
提出日時 2023-12-02 14:55:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,639 bytes
コンパイル時間 1,831 ms
コンパイル使用メモリ 145,124 KB
最終ジャッジ日時 2025-02-18 04:05:45
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<numeric>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<bitset>
#include<random>
#include<functional>
#include<utility>
using namespace std;
void solve()
{
	int N = 2;
	map<int,vector<int>> tate[2],yoko[2],xpy[4],xmy[4];
	for(int i = 0;i < N;i++)
	{
		int x,y;
		char c;
		cin >> x >> y >> c;
		if(c == 'U') tate[0][x].push_back(y),xpy[0][x+y].push_back(x),xmy[0][x-y].push_back(x);
		else if(c == 'D') tate[1][x].push_back(y),xpy[1][x+y].push_back(x),xmy[1][x-y].push_back(x);
		else if(c == 'R') yoko[0][y].push_back(x),xpy[2][x+y].push_back(x),xmy[2][x-y].push_back(x);
		else yoko[1][y].push_back(x),xpy[3][x+y].push_back(x),xmy[3][x-y].push_back(x);
	}
	for(int i = 0;i < 2;i++)
	{
		for(auto &[x,v]:tate[i]) sort(v.begin(),v.end());
		for(auto &[y,v]:yoko[i]) sort(v.begin(),v.end());
	}
	for(int i = 0;i < 4;i++)
	{
		for(auto &[xy,v]:xpy[i]) sort(v.begin(),v.end());
		for(auto &[xy,v]:xmy[i]) sort(v.begin(),v.end());
	}
	int ans = __INT_MAX__;
	for(const auto &[x,v]:tate[0])
	{
		if(!tate[1].count(x)) continue;
		for(int y:v)
		{
			auto it = lower_bound(tate[1][x].begin(),tate[1][x].end(),y);
			if(it == tate[1][x].end()) break;
			ans = min(ans,(*it-y)*5);
		}
	}
	for(const auto &[y,v]:yoko[0])
	{
		if(!yoko[1].count(y)) continue;
		for(int x:v)
		{
			auto it = lower_bound(yoko[1][y].begin(),yoko[1][y].end(),x);
			if(it == yoko[1][y].end()) break;
			ans = min(ans,(*it-x)*5);
		}
	}
	for(const auto &[x,v]:tate[0])
	{
		for(int y:v)
		{
			if(xpy[2].count(x+y))
			{
				auto it = lower_bound(xpy[2][x+y].begin(),xpy[2][x+y].end(),x);
				if(it != xpy[2][x+y].begin())
				{
					it--;
					ans = min(ans,(x-*it)*10);
				}
			}
			if(xmy[3].count(x-y))
			{
				auto it = lower_bound(xmy[3][x-y].begin(),xmy[3][x-y].end(),x);
				if(it != xmy[3][x-y].end()) ans = min(ans,(*it-x)*10);
			}
		}
	}
	for(const auto &[x,v]:tate[1])
	{
		for(int y:v)
		{
			if(xpy[3].count(x+y))
			{
				auto it = lower_bound(xpy[3][x+y].begin(),xpy[3][x+y].end(),x);
				if(it != xpy[3][x+y].end()) ans = min(ans,(*it-x)*10);
			}
			if(xmy[2].count(x-y))
			{
				auto it = lower_bound(xmy[2][x-y].begin(),xmy[2][x-y].end(),x);
				if(it != xmy[2][x-y].begin())
				{
					it--;
					ans = min(ans,(x-*it)*10);
				}
			}
		}
	}
	if(ans == __INT_MAX__) cout << "No\n";
	else cout << "Yes" << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	cin >> tt;
	while(tt--) solve();
}
0