제출 #1137635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137635		hynmj	Naval battle (CEOI24_battle)	C++20	46 / 100	1646 ms	1114112 KiB

Main

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll int 
#define ln cout<<endl
// #define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
// const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
struct ship
{
    int x, y, p;
};

int canSink(const ship &a, const ship &b)
{
    if (a.p==1)
    {
        if (b.p==2)
        {
            if (b.y==a.y and a.x<=b.x)
            return (b.x-a.x)/2;
            
        }
        else if (b.p==3)
        {
            // cout <<"hayan"<<endl;
            if (b.x-a.x == a.y-b.y and b.x-a.x>0)
            return (b.x-a.x);
        }
        else if (b.p==4 and b.x-a.x>0)
        {
            if (b.x-a.x == b.y-a.y)
            {
                return (b.x-a.x);
            }
        }
         return -1;
    }
    else if (a.p==2)
    {
        if (b.p==1)
        {
            if (b.y==a.y and a.x>=b.x)
            return (a.x-b.x)/2;
        }
        else if (b.p==3)
        {
            if (a.x-b.x == a.y-b.y and a.x-b.x>0)
            return (a.x-b.x);
        }
        else if (b.p==4)
        {
            if (a.x-b.x == b.y-a.y and a.x-b.x>0)
            return (a.x-b.x);
        }
        return -1;
    }
     else if (a.p==3)
    {
        if (b.p==4)
        {
            if (b.x==a.x and b.y>=a.y)
            return (b.y-a.y)/2;
        }
        else if (b.p==2)
        {
            if (b.x-a.x == b.y-a.y and b.y-a.y>0)
            return (b.y-a.y);
        }
        else if (b.p==1)
        {
            if (a.x-b.x == b.y-a.y and a.x-b.x>0)
            return (b.y-a.y);
        }
        return -1;
    }
    else if (a.p==4)
    {
        if (b.p==3)
        {
            if (b.x==a.x and b.y<=a.y)
            return (a.y-b.y)/2;
        }
        else if (b.p==2)
        {
            if (b.x-a.x == a.y-b.y and a.y-b.y>0)
            return (a.y-b.y);
        }
        else if (b.p==1)
        {
            if (a.x-b.x == a.y-b.y and a.y-b.y>0)
            return (a.y-b.y);
        }
        return -1;
    }
    return -1;
}
void solve()
{
    int n, k, e, m, ans = 0;
    cin >> n;
    vector<ship> a(n);
    int x,y,z;
    char p;
    bool ok =1;
    rep(n)
    {
    	cin >> a[i].x >> a[i].y >> p;
         if (p=='E')
            z=1;
        if (p=='W')
            z=2;
        if (p=='N')
            z=4,ok=0;
        if (p=='S')
            z=3,ok=0;
        a[i].p=z;
    // cout << a[i].x << " " << a[i].y <<" "<<p;ln;
    }

    vector<vi> shipsToSink;
    if (ok)
    {
        map<int,set<pi>> l;
        map<int,set<pi>> r;
        rep(n)
        {
            if (a[i].p==1)
            r[a[i].x].insert({a[i].y,i+1});
            else l[a[i].x].insert({a[i].y,i+1});
        }
        for (auto it: r)
        {
            for (pi i:it.ss)
            {
                auto k= l[it.ff].upper_bound(i);
                if (k!=l[it.ff].end())
                {
                    shipsToSink.append({((*k).ff )- i.ff , i.ss, (*k).ss});
                }
            }
        }
        for (auto it: l)
        {
            for (pi i:it.ss)
            {
                auto k= r[it.ff].upper_bound(i);
                if (k!=r[it.ff].end())
                {
                    shipsToSink.append({((*k).ff )- i.ff , i.ss, (*k).ss});
                }
            }
        }
    }
    else 
    {
        rep(i,n)
        {
            rep(j,i+1,n)
            {
                int time = canSink(a[i],a[j]); 
                if (time ==-1)
                    continue;
                shipsToSink.append({time,i+1,j+1});
                // assert(time>0 or a[i].p!=1 or a[j].p!=3);
                // cout << a[i].idx<<" "<<a[j].idx <<" " << time<<endl;
            }
        }
    }

    sort(all(shipsToSink));
    set<int> deadShips;
    int nnn = shipsToSink.size();  
    for (int i=0;i<nnn;i++)
    {
        int j=i;
        set<int> atDeath;
        // cout <<"time "<< shipsToSink[i][0]<<endl;

        while (j<nnn and shipsToSink[i][0]==shipsToSink[j][0])
        {
            if (!(deadShips.count(shipsToSink[j][1]) or deadShips.count(shipsToSink[j][2])))
            {
                atDeath.insert(shipsToSink[j][1]);
                atDeath.insert(shipsToSink[j][2]);
            }
            j++;
        }
        for (auto i: atDeath)
        {
            // cout <<i<<" ";
            deadShips.insert(i);
        }
        // ln;
        i=j-1;

    }

    rep(n)
    {
        if  (deadShips.count(i+1)==0)
        {
            cout << i+1 << "\n";
        }  
    }
    // cout << canSink(a[0],a[1]);ln;

    // cout << a[0].p << " " << a[1].p ;ln;

     // cout << ans;
    // cout << a.size();
    // for (auto i: a){cout << i << " ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();}}

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