結果

問題 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0