Submission #1237278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237278		Gray	Naval battle (CEOI24_battle)	C++20	46 / 100	3098 ms	127028 KiB

Main

#include<bits/stdc++.h>

#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;
const ll INF = 2e18;

void solve(){
    ll n; cin >> n;
    vector<array<ll, 3>> a(n);
    vector<map<ll, set<pair<ll, ll>>>> dir(4);
    vector<map<ll, set<pair<ll, ll>>>> diag1(4), diag2(4);
    for (ll i=0; i<n; i++){
        cin >> a[i][0] >> a[i][1];
        swap(a[i][0], a[i][1]);
        char x; cin >> x;
        if (x=='N') {
            a[i][2]=0;
            dir[a[i][2]][a[i][1]].insert({a[i][0], i});
        }
        else if (x=='E') {
            a[i][2]=1;
            dir[a[i][2]][a[i][0]].insert({a[i][1], i});
        }
        else if (x=='S') {
            a[i][2]=2;
            dir[a[i][2]][a[i][1]].insert({a[i][0], i});
        }
        else {
            a[i][2]=3;
            dir[a[i][2]][a[i][0]].insert({a[i][1], i});
        }
        diag1[a[i][2]][a[i][0]+a[i][1]].insert({a[i][1], i});
        diag2[a[i][2]][a[i][0]-a[i][1]].insert({a[i][1], i});
    }
    set<ll> left;
    for (ll i=0; i<n; i++) left.insert(i);
    while (!left.empty()){
        ll mn=INF; set<ll> infl;
        for (ll i=1; i<=2; i++){
            for (auto &[di, st]:dir[i]){
                for (auto [num, ind]:st){
                    ll adi = (i+2)%4;
                    auto iter = dir[adi][di].lower_bound({num, INF});
                    if (iter!=dir[adi][di].end()) {
                        if (mn>(*iter).ff-num){
                            mn=(*iter).ff-num; infl.clear(); 
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }else if (mn==(*iter).ff-num){
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }
                    }
                }
            }
        }
        for (auto ldi:{0, 1}){
            ll adi = (ldi==0?3:2);
            for (auto &[x, st]:diag1[ldi]){
                for (auto [num, ind]:st){
                    auto iter = diag1[adi][x].lower_bound({num, INF});
                    if (iter!=diag1[adi][x].end()){
                        if (mn>((*iter).ff-num)*2){
                            mn=((*iter).ff-num)*2; infl.clear(); 
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }else if (mn==((*iter).ff-num)*2){
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }
                    }
                }
            }
        }
        for (auto ldi:{1, 2}){
            ll adi = (ldi==2?3:0);
            for (auto &[x, st]:diag2[ldi]){
                for (auto [num, ind]:st){
                    auto iter = diag2[adi][x].lower_bound({num, INF});
                    if (iter!=diag2[adi][x].end()){
                        if (mn>((*iter).ff-num)*2){
                            mn=((*iter).ff-num)*2; infl.clear(); 
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }else if (mn==((*iter).ff-num)*2){
                            infl.insert(ind);
                            infl.insert((*iter).ss);
                        }
                    }
                }
            }
        }
        if (infl.empty()) break;
        for (auto ind:infl){
            dir[a[ind][2]][(a[ind][2]%2?a[ind][0]:a[ind][1])].erase({(a[ind][2]%2?a[ind][1]:a[ind][0]), ind});
            diag1[a[ind][2]][a[ind][1]+a[ind][0]].erase({a[ind][1], ind});
            diag2[a[ind][2]][a[ind][0]-a[ind][1]].erase({a[ind][1], ind});
            left.erase(ind);
        }
    }
    for (auto x:left) cout << x+1 << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1; 
    // cin >> t;
    while (t--){
        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