Submission #1213482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213482		spetr	Naval battle (CEOI24_battle)	C++20	46 / 100	1121 ms	1114112 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;

    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";
        }
    }


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