Submission #1213496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213496		spetr	Naval battle (CEOI24_battle)	C++20	76 / 100	698 ms	106480 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>

ll pow(ll x, ll n, ll mod){
    if (n == 0){
        return 1;
    }
ll half = pow(x, n / 2, mod);
ll half_square = (half * half) % mod;

if (n % 2 == 0) {
    return half_square;
} else {
    return (half_square * x) % mod;
}
}   


ll inversion_x(ll x, ll m){
    ll vysledek = pow(x,m-2);
    return vysledek;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    if (N <= 5000){
    vll e,w,n,s;

    vector<bool> ans;
    for (ll i = 0; i < N; i++){
        ll x,y;
        char z;

        cin >> x >> y >> z;
        if (z == 'W'){
            w.push_back({x,y,i});
        }
        if (z == 'E'){
            e.push_back({x,y,i});
        }
        if (z == 'S'){
            s.push_back({x,y,i});
        }
        if (z == 'N'){
            n.push_back({x,y,i});
        }

        ans.push_back(true);
    }


    vll kolize;
    for (ll i = 0; i < n.size(); i++){  
        for (ll j = 0; j < w.size(); j++){
            if (n[i][0] - w[j][0] == w[j][1] - n[i][1] &&  w[j][1] - n[i][1] < 0){
                kolize.push_back({abs(n[i][0] - w[j][0]), w[j][2], n[i][2]});
            }
        }
        for (ll j = 0; j < e.size(); j++){
            if (e[j][0] - n[i][0] ==  e[j][1] - n[i][1] &&  e[j][1] - n[i][1] < 0){
                kolize.push_back({abs(e[j][0] - n[i][0]), e[j][2], n[i][2]});
            }
        }
    }

    for (ll i = 0; i < s.size(); i++){  
        for (ll j = 0; j < w.size(); j++){
            if (s[i][0] - w[j][0] == s[i][1] - w[j][1] &&  s[i][1] - w[j][1] < 0){
                kolize.push_back({abs(s[i][0] - w[j][0]), w[j][2], s[i][2]});
            }
        }
        for (ll j = 0; j < e.size(); j++){
            if ((e[j][0] - s[i][0]) == (s[i][1] - e[j][1]) &&  s[i][1] - e[j][1] < 0){
                kolize.push_back({abs(e[j][0] - s[i][0]), e[j][2], s[i][2]});
            }
        }
    }


    for (ll i = 0; i < n.size(); i++){
        for (ll j = 0; j < s.size(); j++){
            if (n[i][0] == s[j][0] && n[i][1] > s[j][1]){
                kolize.push_back({abs(n[i][1] - s[j][1])/2, n[i][2], s[j][2]});
            }
        }
    }


    for (ll i = 0; i < e.size(); i++){
        for (ll j = 0; j < w.size(); j++){
            if (e[i][1] == w[j][1] && w[j][0] > e[i][0]){
                kolize.push_back({abs(w[j][0] - e[i][0])/2, e[i][2], w[j][2]});
            }
        }
    }

    sort(kolize.begin(), kolize.end());

    set<ll> mnozina;
    ll cas;
    for (ll i = 0; i < kolize.size(); i+=0){
        cas = kolize[i][0];
        while (i < kolize.size() && kolize[i][0] == cas){
            if (ans[kolize[i][1]] == true && ans[kolize[i][2]] == true){
                mnozina.insert(kolize[i][1]);
                mnozina.insert(kolize[i][2]);
            }
            i++;
        }

        for (ll prvek : mnozina){
            ans[prvek] = false;
        }
        mnozina.clear();
    }

    for (ll i = 0; i<N; i++){
        if (ans[i] == true){
            cout << i+1 << "\n";
        }
    }}

    else{
        vll lode;

        for (ll i = 0; i < N; i++){
            ll x,y;
            char znak;
            cin >> x >> y >> znak;
            if (znak == 'E'){
                lode.push_back({x,y,i,1});
            }
            else{
                lode.push_back({x,y,i,0});
            }
        }

        sort(lode.begin(), lode.end());

        map<ll, vll> mapa;
        set<ll> mnozina;
        for (ll i = 0; i < N; i++){
            auto exist = mnozina.find(lode[i][0] + lode[i][1]);
            if (exist == mnozina.end()){
                mapa[lode[i][0] + lode[i][1]] = {lode[i]};
                mnozina.insert(lode[i][0] + lode[i][1]);
            }
            else{
                mapa[lode[i][0] + lode[i][1]].push_back(lode[i]);
            }
        }

        vector<bool> ans;
        for (ll i = 0; i<N; i++) ans.push_back(true);
        for (const auto& [k, diago] : mapa){
            vll stack; // E jsou 1
            for (ll i = 0; i < diago.size(); i++){
                if (diago[i][3] == 1){
                    stack.push_back(diago[i]);
                }

                else{
                    if (stack.size()>0){
                        ans[diago[i][2]] = false;
                        ans[stack[stack.size()-1][2]] = false;
                        stack.pop_back();
                    }
                }
            }

        }

        for (ll i = 0; i < N; i++){
            if (ans[i] == true){
                cout << i+1 << "\n";
            }
        }

    }


    return 0;
}

• 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