Submission #1134349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134349		ReLice	Naval battle (CEOI24_battle)	C++20	20 / 100	43 ms	12216 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

void solve() {
    ll i, j;

    ll n;
    cin>>n;

    ll x[n + 1], y[n + 1];
    ll d[n + 1];

    vector<ll> vv;
    vector<ar<ll, 3>> ans;

    bool ff = 1;

    for(i=1;i<=n;i++){
        char ch;
        cin>>x[i]>>y[i]>>ch;

        if(ch == 'N') d[i] = 0;
        if(ch == 'S') d[i] = 1;
        if(ch == 'W') d[i] = 2;
        if(ch == 'E') d[i] = 3;

        if(ch == 'N') ff = 0;
        if(ch == 'W') ff = 0;

        vv.pb(x[i] + y[i]);
    }

    if(ff){
        sort(all(vv));
        vv.erase(unique(all(vv)), vv.end());

        map<ll,ll> pos;
        for(i=0;i<vv.size();i++){
            pos[vv[i]] = i;
        }

        vector<vector<pair<ll,ll>>> v(vv.size()), h(vv.size());

        for(i=1;i<=n;i++){
            if(d[i] == 1) v[pos[x[i] + y[i]]].pb({x[i], i});
            else h[pos[x[i] + y[i]]].pb({x[i], i});
        }

        for(i=0;i<vv.size();i++) sort(all(vv));

        for(i=0;i<vv.size();i++){
            ll a = 0, b = 0;
            while(a < v[i].size()){

                while(b < h[i].size() && v[i][a].fr >= h[i][b].fr) b++;

                if(b == h[i].size()) break;

                ans.pb({h[i][b].fr - v[i][a].fr, v[i][a].sc, h[i][b].sc});

                a++;
            }
        }
    }

    else{
        for(i=1;i<=n;i++){
            for(j=i + 1;j<=n;j++){
                if(d[i] == d[j]) continue;

                if(d[i] > d[j]) swap(i, j);

                if(d[i] == 0 && d[j] == 1 && x[i] == x[j] && y[j] < y[i]){
                    ans.pb({(y[i] - y[j]) / 2, i, j});
                }
                if(d[i] == 2 && d[j] == 3 && y[i] == y[j] && x[i] > x[j]){
                    ans.pb({(x[i] - x[j]) / 2, i, j});
                }

                if(d[i] <= 1 && d[j] >= 2){
                    bool f = 0;

                    if(d[i] == 0 && d[j] == 2 && x[j] - x[i] == y[i] - y[j] && x[j] > x[i]) f = 1;
                    if(d[i] == 0 && d[j] == 3 && x[i] - x[j] == y[i] - y[j] && x[i] > x[j]) f = 1;
                    if(d[i] == 1 && d[j] == 2 && x[j] - x[i] == y[j] - y[i] && x[j] > x[i]) f = 1;
                    if(d[i] == 1 && d[j] == 3 && x[i] - x[j] == y[j] - y[i] && x[i] > x[j]) f = 1;

                    if(f){
                        ans.pb({abs(x[i] - x[j]), i, j});
                    }
                }

                if(i > j) swap(i, j);
            }
        }
    }

    vector<bool> f(n + 1, true);

    sort(rall(ans));

    while(ans.size()){
        vector<ll> vv;

        ll x = ans.back()[0];

        while(ans.size() && ans.back()[0] == x){
            i = ans.back()[1], j = ans.back()[2];

            ans.pop_back();

            if(f[i] && f[j]){
                vv.pb(i);
                vv.pb(j);
            }
        }

        for(auto i : vv){
            f[i] = 0;
        }
    }

    for(i=1;i<=n;i++) {
        if(f[i]) cout<<i<<endl;
    }


}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*


*/

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