Submission #1138204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138204		Sir_Ahmed_Imran	Naval battle (CEOI24_battle)	C++20	36 / 100	2838 ms	173936 KiB

Main

                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;

#define N 1000001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

// N E S W
int a[N];
int b[N];
int c[N];
map<int, vector<int>> t;
map<int, set<int>> xy[4];
map<int, set<int>> yx[4];
map<int, set<int>> x[4][2];
map<int, set<int>> y[4][2];

int lst(set<int> & s, int v){
    auto it = s.upper_bound(v);
    if(it == s.begin()) return -1;
    return *(--it);
}

int nxt(set<int> & s, int v){
    auto it = s.upper_bound(v);
    if(it == s.end()) return -1;
    return *it;
}

int crash(int p, int q, int r){
    int m, ans;
    ans = 1e9 + 1;
    if(r == 0){
        m = lst(x[2][q & 1][p], q);
        if(m >= 0) ans = min(ans, (q - m) / 2);
        m = lst(xy[3][p + q], q);
        if(m >= 0) ans = min(ans, (q - m));
        m = lst(yx[1][p - q], p);
        if(m >= 0) ans = min(ans, (p - m));
    }
    if(r == 1){
        m = nxt(y[3][p & 1][q], p);
        if(m >= 0) ans = min(ans, (m - p) / 2);
        m = lst(xy[2][p + q], q);
        if(m >= 0) ans = min(ans, (q - m));
        m = nxt(yx[0][p - q], p);
        if(m >= 0) ans = min(ans, (m - p));
    }
    if(r == 2){
        m = nxt(x[0][q & 1][p], q);
        if(m >= 0) ans = min(ans, (m - q) / 2);
        m = nxt(xy[1][p + q], q);
        if(m >= 0) ans = min(ans, (m - q));
        m = nxt(yx[3][p - q], p);
        if(m >= 0) ans = min(ans, (m - p));
    }
    if(r == 3){
        m = lst(x[1][p & 1][q], p);
        if(m >= 0) ans = min(ans, (p - m) / 2);
        m = nxt(xy[0][p + q], q);
        if(m >= 0) ans = min(ans, (m - q));
        m = lst(yx[2][p - q], p);
        if(m >= 0) ans = min(ans, (p - m));
    }
    return ans;
}

void solve(){
    char d;
    int n, m, p, q, r;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> p >> q >> d;
        a[i] = p, b[i] = q;
        if(d == 'N') c[i] = 0;
        if(d == 'E') c[i] = 1;
        if(d == 'S') c[i] = 2;
        if(d == 'W') c[i] = 3;
        xy[c[i]][p + q].add(q);
        yx[c[i]][p - q].add(p);
        x[c[i]][q & 1][p].add(q);
        y[c[i]][p & 1][q].add(p);
    }
    for(int i = 1; i <= n; i++)
        t[crash(a[i], b[i], c[i])].append(i);
    vector<int> v; 
    while(!t.empty()){
        m = (*t.begin()).ff;
        if(m > 1e9) break;
        for(auto & i : t[m]){
            r = crash(a[i], b[i], c[i]); 
            if(r == m) v.append(i);
            else t[r].append(i);
        }
        for(auto & i : v){
            p = a[i], q = b[i];
            xy[c[i]][p + q].erase(q);
            yx[c[i]][p - q].erase(p);
            x[c[i]][q & 1][p].erase(q);
            y[c[i]][p & 1][q].erase(p);
        }
        t.erase(m);
        v.clear();
    }
    for(auto & i : t[1e9 + 1])
        cout << i << nl;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

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