제출 #1311822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311822		HoriaHaivas	Naval battle (CEOI24_battle)	C++20	6 / 100	2 ms	584 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct nava
{
    int x;
    int y;
    char dir;
};

struct muchie
{
    int to;
    int cost;
};

struct nsuh
{
    int a;
    int b;
    int when;
};

bool cmp(nsuh a, nsuh b)
{
    return a.when<b.when;
}

nava ship[5005];
vector<muchie> nodes[5005];
vector<nsuh> edges;
int collided[5005];

int collision(nava a, nava b)
{
    if (a.dir==b.dir)
        return -1;
    int diff;
    if (a.dir=='E' && b.dir=='W' || a.dir=='W' && b.dir=='E')
    {
        if (a.dir=='W')
            swap(a,b);
        if (a.x==b.x && a.y<=b.y)
        {
            diff=b.y-a.y;
            if (diff%2==0)
                return (a.y+diff/2);
            else
                return -1;
        }
        else
            return -1;
    }
    if (a.dir=='S' && b.dir=='N' || a.dir=='N' && b.dir=='S')
    {
        if (a.dir=='N')
            swap(a,b);
        if (a.y==b.y && a.x<=b.x)
        {
            diff=b.x-a.x;
            if (diff%2==0)
                return (a.x+diff/2);
            else
                return -1;
        }
        else
            return -1;
    }
    if (a.dir=='E' && b.dir=='N' || a.dir=='N' && b.dir=='E')
    {
        if (a.dir=='N')
            swap(a,b);
        if (a.x<=b.x && a.y<=b.y)
        {
            if ((b.x-a.x)==(b.y-a.y))
                return (b.x-a.x);
            else
                return -1;
        }
        else
            return -1;
    }
    if (a.dir=='E' && b.dir=='S' || a.dir=='S' && b.dir=='E')
    {
        if (a.dir=='S')
            swap(a,b);
        if (a.x>=b.x && a.y<=b.y)
        {
            if ((a.x-b.x)==(b.y-a.y))
                return (a.x-b.x);
            else
                return -1;
        }
        else
            return -1;
    }
    if (a.dir=='W' && b.dir=='N' || a.dir=='N' && b.dir=='W')
    {
        if (a.dir=='N')
            swap(a,b);
        if (a.x<=b.x && a.y>=b.y)
        {
            if ((b.x-a.x)==(a.y-b.y))
                return (b.x-a.x);
            else
                return -1;
        }
        else
            return -1;
    }
    if (a.dir=='W' && b.dir=='S' || a.dir=='S' && b.dir=='W')
    {
        if (a.dir=='S')
            swap(a,b);
        if (a.x>=b.x && a.y>=b.y)
        {
            if((a.x-b.x)==(a.y-b.y))
                return (a.x-b.x);
            else
                return -1;
        }
        else
            return -1;
    }
    assert(0);
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,rez,when;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> ship[i].x >> ship[i].y >> ship[i].dir;
        swap(ship[i].x,ship[i].y);
    }
    for (i=1; i<=n; i++)
    {
        for (j=i+1; j<=n; j++)
        {
            when=collision(ship[i],ship[j]);
            if (when!=-1)
            {
                nodes[i].push_back({j,when});
                nodes[j].push_back({i,when});
                edges.push_back({i,j,when});
            }
        }
    }
    sort(edges.begin(),edges.end(),cmp);
    for (auto x : edges)
    {
         if (collided[x.a]==x.when && !collided[x.b] || collided[x.b]==x.when && !collided[x.a] || !collided[x.a] && !collided[x.b])
         {
             collided[x.a]=x.when;
             collided[x.b]=x.when;
         }
    }
    for (i=1;i<=n;i++)
    {
         if (!collided[i])
             cout << i << "\n";
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24