Submission #1137586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137586		Muhammad_Aneeq	Naval battle (CEOI24_battle)	C++20	76 / 100	3118 ms	471420 KiB

Main

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#warning check the output
using namespace std;
int const N=2e5+10;
int x[N],y[N];
char c[N];
set<pair<int,int>>vals[N]={};
bool ans[N]={};
void check(int i,int j)
{
    if (c[i]==c[j])
        return;
    if (c[i]=='N')
    {
        if (c[j]=='S'&&x[i]==x[j]&&y[j]<y[i]&&(y[i]-y[j])%2==0)
        {
            int cur=abs(y[i]-y[j])/2;
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='E'&&x[i]>x[j]&&y[i]>y[j]&&x[i]-x[j]==y[i]-y[j])
        {
            int cur=x[i]-x[j];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='W'&&x[j]>x[i]&&y[i]>y[j]&&x[j]-x[i]==y[i]-y[j])
        {
            int cur=x[j]-x[i];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
    }
    if (c[i]=='S')
    {
        if (c[j]=='N'&&x[i]==x[j]&&y[j]>y[i]&&(y[j]-y[i])%2==0)
        {
            int cur=abs(y[i]-y[j])/2;
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='E'&&x[i]>x[j]&&y[i]<y[j]&&x[i]-x[j]==y[j]-y[i])
        {
            int cur=x[i]-x[j];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='W'&&x[j]>x[i]&&y[i]<y[j]&&x[j]-x[i]==y[j]-y[i])
        {
            int cur=x[j]-x[i];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
    }
    if (c[i]=='E')
    {
        if (c[j]=='S'&&x[i]<x[j]&&y[i]>y[j]&&x[j]-x[i]==y[i]-y[j])
        {
            int cur=x[j]-x[i];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='N'&&x[j]>x[i]&&y[j]>y[i]&&x[j]-x[i]==y[j]-y[i])
        {
            int cur=x[j]-x[i];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='W'&&x[j]>x[i]&&y[i]==y[j]&&(x[j]-x[i])%2==0)
        {
            int cur=(x[j]-x[i])/2;
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
    }
    if (c[i]=='W')
    {
        if (c[j]=='S'&&x[i]>x[j]&&y[i]>y[j]&&x[i]-x[j]==y[i]-y[j])
        {
            int cur=x[i]-x[j];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='N'&&x[j]<x[i]&&y[j]>y[i]&&x[i]-x[j]==y[j]-y[i])
        {
            int cur=x[i]-x[j];
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
        if (c[j]=='E'&&x[j]<x[i]&&y[i]==y[j]&&(x[i]-x[j])%2==0)
        {
            int cur=(x[i]-x[j])/2;
            vals[i].insert({cur,j});
            vals[j].insert({cur,i});
        }
    }
}
void subt6(int n)
{
    map<int,vector<pair<int,int>>>e;
    map<int,set<pair<int,int>>>s;
    for (int i=0;i<n;i++)
    {
        if (c[i]=='S')
        {
            s[x[i]+y[i]].insert({x[i],i});
        }
        else
        {
            e[x[i]+y[i]].push_back({x[i],i});
        }
    }
    for (auto& [i,k]:e)
    {
        sort(rbegin(k),rend(k));
        for (auto [j,ind]:k)
        {
            auto z=s[i].lower_bound({j,-1});
            if (z==s[i].end())
                continue;
            ans[ind]=ans[(*z).second]=1;
            s[i].erase(z);
        }
    }
    for (int i=0;i<n;i++)
    {
        if (ans[i]==0)
        {
            cout<<i+1<<endl;
        }
    }
}
inline void solve()
{
    int n;
    cin>>n;
    bool s6=1;
    for (int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i]>>c[i];
        if (c[i]=='N'||c[i]=='W')
            s6=0;
    }
    if (s6)
    {
        subt6(n);
        return;
    }
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            check(i,j);
        }
    }
    while (1)
    {
        int mn=1e9+10;
        vector<int>inds;
        for (int i=0;i<n;i++)
        {
            if (vals[i].size()&&(*begin(vals[i])).first<mn)
            {
                inds={};
                mn=(*begin(vals[i])).first;
                inds.push_back(i);
            }
            else if (mn==(*begin(vals[i])).first)
            {
                inds.push_back(i);
            }
        }
        if (inds.size()==0)
            break;
        for (auto i:inds)
        {
            ans[i]=1;
            for (auto [j,k]:vals[i])
                vals[k].erase({j,i});
            vals[i]={};
        }
    }
    for (int i=0;i<n;i++)
    {
        if (ans[i]==0)
        {
            cout<<i+1<<endl;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

Main.cpp:12:2: warning: #warning check the output [-Wcpp]
   12 | #warning check the output
      |  ^~~~~~~

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