Submission #1230979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230979		PVM_pvm	Naval battle (CEOI24_battle)	C++20	6 / 100	3062 ms	791588 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
struct ship
{
    int x,y;
    int tp; ///N 0, E 1, S 2, W 3
    int ind;
} sh[MAXN];
int n;
int kg[MAXN];
struct event
{
    int vreme;
    int k1,k2;
};
bool operator<(event a, event b)
{
    return a.vreme>b.vreme;
}
bool operator>(event a, event b)
{
    return a.vreme<b.vreme;
}
int main()
{
    cin>>n;
    for (int q=1;q<=n;q++)
    {
        sh[q].ind=q;
        cin>>sh[q].x>>sh[q].y;
        char c;
        cin>>c;
        if (c=='N') sh[q].tp=0;
        else if (c=='E') sh[q].tp=1;
        else if (c=='S') sh[q].tp=2;
        else if (c=='W') sh[q].tp=3;
    }
    priority_queue<event> qu;
    for (int q=1;q<=n;q++)
    {
        for (int w=1;w<=n;w++)
        {
            if (q==w) continue;
            if (sh[q].tp==sh[w].tp) continue;
            if (sh[q].tp==0)
            {
                if (sh[w].tp==2)
                {
                    if (sh[q].x!=sh[w].x) continue;
                    if ((sh[q].y%2)!=(sh[w].y%2)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    dff/=2;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==1)
                {
                    if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==3)
                {
                    if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
            }
            if (sh[q].tp==2)
            {
                if (sh[w].tp==0)
                {
                    if (sh[q].x!=sh[w].x) continue;
                    if ((sh[q].y%2)!=(sh[w].y%2)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    dff/=2;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==1)
                {
                    if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==3)
                {
                    if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
            }
            if (sh[q].tp==1)
            {
                if (sh[w].tp==3)
                {
                    if (sh[q].y!=sh[w].y) continue;
                    if ((sh[q].x%2)!=(sh[w].x%2)) continue;
                    int dff=sh[q].x-sh[w].x;
                    if (dff<0) dff*=-1;
                    dff/=2;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==0)
                {
                    if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==2)
                {
                    if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
            }
            if (sh[q].tp==3)
            {
                if (sh[w].tp==1)
                {
                    if (sh[q].y!=sh[w].y) continue;
                    if ((sh[q].x%2)!=(sh[w].x%2)) continue;
                    int dff=sh[q].x-sh[w].x;
                    if (dff<0) dff*=-1;
                    dff/=2;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==2)
                {
                    if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
                if (sh[w].tp==0)
                {
                    if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                    int dff=sh[q].y-sh[w].y;
                    if (dff<0) dff*=-1;
                    qu.push({dff,q,w});
                }
            }
        }
    }
    while (!qu.empty())
    {
        //for (int q=1;q<=n;q++) cout<<kg[q]<<" ";
        //cout<<"\n";
        event tp=qu.top();
        qu.pop();
        assert(tp.vreme!=0);
        //cout<<tp.k1<<" "<<tp.k2<<" "<<tp.vreme<<"\n";
        if (kg[ tp.k1 ]!=0 && kg[tp.k2]!=0) continue;
        if (kg[tp.k1]!=0)
        {
            if (tp.vreme==kg[tp.k1])
            {
                kg[tp.k2]=tp.vreme;
            }
            continue;
        }
        if (kg[tp.k2]!=0)
        {
            if (tp.vreme==kg[tp.k2])
            {
                kg[tp.k1]=tp.vreme;
            }
            continue;
        }
        kg[tp.k1]=tp.vreme;
        kg[tp.k2]=tp.vreme;
    }
    for (int q=1;q<=n;q++)
    {
        if (kg[q]==0) cout<<q<<"\n";
    }
}
/*
6
4 0 W
0 2 E
2 2 S
4 4 N
6 6 W
4 2 W
*/

• 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