Submission #1177367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177367		alexdd	Naval battle (CEOI24_battle)	C++20	36 / 100	1616 ms	144412 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int x[200005],y[200005];
char tip[200005];
int scos[200005];
priority_queue<pair<int,pair<int,int>>> pq;///{timp,{id1,id2}}

map<int,set<pair<int,int>>> dE[3],dW[3],dN[3],dS[3];
void calc_vecini(int i)///calculeaza si restu lovirilor-----------------------------------------------------------------
{
    if(tip[i]=='E')
    {
        auto it = dW[0][y[i]].lower_bound({x[i],0});
        if(it != dW[0][y[i]].end())
            pq.push({-((*it).first - x[i])/2, {i, (*it).second}});

        it = dS[2][x[i]+y[i]].lower_bound({x[i],0});
        if(it != dS[2][x[i]+y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});

        it = dN[1][x[i]-y[i]].lower_bound({x[i],0});
        if(it != dN[1][x[i]-y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});
    }
    else if(tip[i]=='W')
    {
        auto it = dE[0][y[i]].lower_bound({x[i],INF});
        if(it != dE[0][y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first)/2, {i, (*it).second}});
        }

        it = dN[2][x[i]+y[i]].lower_bound({x[i],INF});
        if(it != dN[2][x[i]+y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }

        it = dS[1][x[i]-y[i]].lower_bound({x[i],INF});
        if(it != dS[1][x[i]-y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }
    }
    else if(tip[i]=='N')
    {
        auto it = dS[0][x[i]].lower_bound({y[i],INF});
        if(it != dS[0][x[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first)/2, {i, (*it).second}});
        }

        it = dW[2][x[i]+y[i]].lower_bound({x[i],0});
        if(it != dW[2][x[i]+y[i]].end())
            pq.push({-((*it).first - y[i]), {i, (*it).second}});

        it = dE[1][x[i]-y[i]].lower_bound({x[i],INF});
        if(it != dE[1][x[i]-y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }
    }
    else
    {
        assert(tip[i]=='S');

        auto it = dN[0][x[i]].lower_bound({y[i],0});
        if(it != dN[0][x[i]].end())
            pq.push({-((*it).first - y[i])/2, {i, (*it).second}});

        it = dE[2][x[i]+y[i]].lower_bound({x[i],INF});
        if(it != dE[2][x[i]+y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }

        it = dW[1][x[i]-y[i]].lower_bound({x[i],0});
        if(it != dW[1][x[i]-y[i]].end())
            pq.push({-((*it).first - y[i]), {i, (*it).second}});
    }
}
void baga(int i)
{
    if(tip[i]=='E')
    {
        dE[0][y[i]].insert({x[i],i});
        dE[1][x[i] - y[i]].insert({x[i],i});
        dE[2][x[i] + y[i]].insert({x[i],i});
    }
    else if(tip[i]=='W')
    {
        dW[0][y[i]].insert({x[i],i});
        dW[1][x[i] - y[i]].insert({x[i],i});
        dW[2][x[i] + y[i]].insert({x[i],i});
    }
    else if(tip[i]=='N')
    {
        dN[0][x[i]].insert({y[i],i});
        dN[1][x[i] - y[i]].insert({x[i],i});
        dN[2][x[i] + y[i]].insert({x[i],i});
    }
    else
    {
        assert(tip[i]=='S');
        dS[0][x[i]].insert({y[i],i});
        dS[1][x[i] - y[i]].insert({x[i],i});
        dS[2][x[i] + y[i]].insert({x[i],i});
    }
}
void scoate(int i)
{
    if(tip[i]=='E')
    {
        dE[0][y[i]].erase({x[i],i});
        dE[1][x[i] - y[i]].erase({x[i],i});
        dE[2][x[i] + y[i]].erase({x[i],i});
    }
    else if(tip[i]=='W')
    {
        dW[0][y[i]].erase({x[i],i});
        dW[1][x[i] - y[i]].erase({x[i],i});
        dW[2][x[i] + y[i]].erase({x[i],i});
    }
    else if(tip[i]=='N')
    {
        dN[0][x[i]].erase({y[i],i});
        dN[1][x[i] - y[i]].erase({x[i],i});
        dN[2][x[i] + y[i]].erase({x[i],i});
    }
    else
    {
        assert(tip[i]=='S');
        dS[0][x[i]].erase({y[i],i});
        dS[1][x[i] - y[i]].erase({x[i],i});
        dS[2][x[i] + y[i]].erase({x[i],i});
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>tip[i];
        baga(i);
    }
    for(int i=1;i<=n;i++)
    {
        calc_vecini(i);
    }
    while(!pq.empty())
    {
        int id1 = pq.top().second.first, id2 = pq.top().second.second;
        pq.pop();
        if(scos[id1] && scos[id2])
        {
            continue;
        }
        else if(!scos[id1] && scos[id2])
        {
            if(scos[id2] == pq.top().first)
            {
                scoate(id1);
                scos[id1] = pq.top().first;
            }
            else
                calc_vecini(id1);
        }
        else if(scos[id1] && !scos[id2])
        {
            if(scos[id1] == pq.top().first)
            {
                scoate(id2);
                scos[id2] = pq.top().first;
            }
            else
                calc_vecini(id2);
        }
        else
        {
            scoate(id1);
            scoate(id2);
            scos[id1] = scos[id2] = pq.top().first;
        }
    }
    for(int i=1;i<=n;i++)
        if(!scos[i])
            cout<<i<<"\n";
    return 0;
}
/**

ca 2 barci sa se loveasca trebuie ele sa fie:
pe aceeasi diagonala daca au directiile de deplasare perpendiculare
pe aceeasi linie daca au directiile de deplasare paralele

pentru fiecare barca tinem cea mai apropiata barca pe fiecare diagonala si pe linie/coloana (3 barci in total)
facem un pq in care bagam asta, il updatam dupa fiecare ciocnire

*/

• 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: 30 / 30
• Subtask 7: 0 / 24