제출 #1026377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026377		12345678	Naval battle (CEOI24_battle)	C++17	30 / 100	170 ms	33504 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, x[nx], y[nx], dn[nx];
char dr[nx];

struct ship
{
    vector<pair<int, int>> s, e;
};
map<int, ship> mp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) 
    {
        cin>>x[i]>>y[i]>>dr[i];
        if (dr[i]=='S') mp[x[i]+y[i]].s.push_back({x[i], i});
        else mp[x[i]+y[i]].e.push_back({x[i], i});
    }
    for (auto &[_, t]:mp)
    {
        //cout<<"debug "<<_<<'\n';
        sort(t.e.begin(), t.e.end());
        sort(t.s.begin(), t.s.end());
        //for (auto x:t.s) cout<<"S "<<x.first<<' '<<x.second<<'\n';
        //for (auto x:t.e) cout<<"E "<<x.first<<' '<<x.second<<'\n';
        stack<int> st;
        while (!t.e.empty()||!t.s.empty())
        {
            //cout<<"s "<<t.e.empty()<<'\n';
            if (t.e.empty()||(!t.s.empty()&&t.s.back()>t.e.back())) st.push(t.s.back().second), t.s.pop_back();
            else
            {
                if (!st.empty()) dn[t.e.back().second]=dn[st.top()]=1, st.pop();
                t.e.pop_back(); 
            }
        }
    }
    for (int i=1; i<=n; i++) if (!dn[i]) cout<<i<<'\n';
}

/*
8
3 0 S
4 0 S
2 1 E
1 2 E
5 2 S
4 3 S
0 5 E
2 5 E
*/

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