Submission #1104145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104145		SoMotThanhXuan	Naval battle (CEOI24_battle)	C++17	76 / 100	274 ms	39240 KiB

Main

// absolutely incredible
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define pb push_back
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
struct Point{
    int x, y;
    char d;
    int intersect(const Point &rhs)const{
        if(d == rhs.d) return 0;
        int temp = abs(x - rhs.x) + abs(y - rhs.y);
        temp >>= 1;
        if(d == 'N'){
            if(rhs.d == 'E'){
                if(y - temp == rhs.y && rhs.x + temp == x) return temp;
                return 0;
            }
            if(rhs.d == 'S'){
                if(y - temp == rhs.y + temp && x == rhs.x) return temp;
                return 0;
            }
            if(y - temp == rhs.y && x == rhs.x - temp) return temp;
            return 0;
        }
        if(d == 'E'){
            if(rhs.d == 'N'){
                if(x + temp == rhs.x && rhs.y - temp == y) return temp;
                return 0;
            }
            if(rhs.d == 'W'){
                if(x + temp == rhs.x - temp && y == rhs.y) return temp;
                return 0;
            }
            if(x + temp == rhs.x && rhs.y + temp == y) return temp;
            return 0;
        }
        if(d == 'S'){
            if(rhs.d == 'N'){
                if(y + temp == rhs.y - temp && x == rhs.x) return temp;
                return 0;
            }
            if(rhs.d == 'E'){
                if(y + temp == rhs.y && rhs.x + temp  == x) return temp;
                return 0;
            }
            if(y + temp == rhs.y && rhs.x - temp == x) return temp;
            return 0;
        }
        if(rhs.d == 'N'){
            if(x - temp == rhs.x && rhs.y - temp == y) return temp;
            return 0;
        }
        if(rhs.d == 'E'){
            if(x - temp == rhs.x + temp && y == rhs.y) return temp;
            return 0;
        }
        if(x - temp == rhs.x && rhs.y + temp == y) return temp;
        return 0;
    }
}p[maxN];
const int INF = INT_MAX;
int N;
namespace subtask12345{
    bool check(){
        return N <= 5000;
    }
    const int maxT = 12497500 + 1;
    pair<int, pair<int, int>> t[maxT];
    int del[maxN];
    void solve(){
        int cnt = 0;
        FOR(i, 1, N){
            FOR(j, i + 1, N){
                int k = p[i].intersect(p[j]);
                if(k > 0)t[++cnt] = {k, {i, j}};
            }
        }
        sort(t + 1, t + 1 + cnt);
        FOR(i, 1, N)del[i] = INF;
        FOR(i, 1, cnt){
            int k = t[i].first;
            int pi = t[i].second.first;
            int pj = t[i].second.second;
            if(del[pi] < k || del[pj] < k)continue;
            del[pi] = del[pj] = k;
        }
        FOR(i, 1, N){
            if(del[i] == INF)cout << i << "\n";
        }

    }

}
namespace subtask6{
    vector<pair<pair<int, int>, int>> v[maxN];
    int comp[maxN];
    bool check(){
        FOR(i, 1, N){
            if(p[i].d == 'S' || p[i].d == 'E') continue;
            return false;
        }
        return true;
    }
    bool del[maxN];
    void solve(){
        FOR(i, 1, N){
            comp[i] = p[i].x + p[i].y;
        }
        sort(comp + 1, comp + 1 + N);
        FOR(i, 1, N){
            int x = lower_bound(comp + 1, comp + 1 + N, p[i].x + p[i].y) - comp;
            v[x].push_back({{p[i].x, p[i].y}, i});
        }
        stack<int> st;
        FOR(i, 1, N){
            sort(v[i].begin(), v[i].end());
            while(st.size())st.pop();
            for(pair<pair<int, int>, int> x : v[i]){
                if(p[x.second].d == 'E')st.push(x.second);
                else{
                    if(!st.empty()){
                        del[st.top()] = del[x.second] = true;
                        st.pop();
                    }
                }
            }
        }
        FOR(i, 1, N){
            if(del[i] == false)cout << i << "\n";
        }
    }
}
namespace subtask7{
    int md[maxN], sd[maxN], hor[maxN], ver[maxN];
    int del[maxN];
    priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> Q;
    int nxt[3][maxN];
    vector<int> v[maxN];
    bool sX(const int &a, const int &b){
        return p[a].x < p[b].x;
    }
    bool gX(const int &a, const int &b){
        return p[a].x > p[b].x;
    }
    bool Y(const int &a, const int &b){
        return p[a].y < p[b].y;
    }
    const int INF = 1e9;
    int val[4][maxN];
    void make_List(char d1, char d2, int type, bool dig){
        FOR(i, 1, N)v[i].clear();
        FOR(i, 1, N){
            if(p[i].d != d1 && p[i].d != d2)continue;
            v[val[type][i]].push_back(i);
        }
        stack<int> st;
        bool sortx = false;
        int dir1, dir2;
        if(dig){
            dir1 = 0;
            dir2 = 2;
        }else dir1 = dir2 = 1;
        if(d1 == 'S' && d2 == 'W')sortx = true;
        else if(d1 == 'W' && d2 == 'N') sortx = false;
        else if(d1 == 'N' && d2 == 'E') sortx = false;
        else if(d1 == 'E' && d2 == 'S') sortx = true;
        else if(d1 == 'E' && d2 == 'W')sortx = true;
        FOR(i, 1, N){
            if(sortx)sort(v[i].begin(), v[i].end(), sX);
            else if(dig) sort(v[i].begin(), v[i].end(), gX);
            else sort(v[i].begin(), v[i].end(), Y);
            while(!st.empty()) st.pop();
            for(int id : v[i]){
                if(p[id].d == d1)st.push(id);
                else{
                    if(!st.empty()){
                        int tp = st.top();
                        st.pop();
                        Q.push({p[id].intersect(p[tp]), tp, id, dir1, dir2});
                    }
                }
            }
            if(dig){
                int lastF = 0, lastS = 0;
                for(int j = 0; j < v[i].size(); ++j){
                    int id = v[i][j];
                    if(p[id].d == d2)continue;
                    nxt[0][id] = lastF;
                    lastF = id;
                }
                for(int j = v[i].size() - 1; j >= 0; --j){
                    int id = v[i][j];
                    if(p[id].d == d1)continue;
                    nxt[2][id] = lastS;
                    lastS = id;
                }
                continue;
            }else{
                if(sortx){
                    int lastF = 0, lastS = 0;
                    for(int j = 0; j < v[i].size(); ++j){
                        int id = v[i][j];
                        if(p[id].d == d2)continue;
                        nxt[1][id] = lastF;
                        lastF = id;
                    }
                    for(int j = v[i].size() - 1; j >= 0; --j){
                        int id = v[i][j];
                        if(p[id].d == d1)continue;
                        nxt[1][id] = lastS;
                        lastS = id;
                    }
                }else{
                    int lastF = 0, lastS = 0;
                    for(int j = 0; j < v[i].size(); ++j){
                        int id = v[i][j];
                        if(p[id].d == d2)continue;
                        nxt[1][id] = lastF;
                        lastF = id;
                    }
                    for(int j = v[i].size() - 1; j >= 0; --j){
                        int id = v[i][j];
                        if(p[id].d == d1)continue;
                        nxt[1][id] = lastS;
                        lastS = id;
                    }
                }
            }

        }
    }
    void solve(){
        FOR(i, 1, N){
            md[i] = p[i].x - p[i].y;
            sd[i] = p[i].x + p[i].y;
            hor[i] = p[i].y;
            ver[i] = p[i].x;
        }
        sort(md + 1, md + 1 + N);
        sort(sd + 1, sd + 1 + N);
        sort(hor + 1, hor + 1 + N);
        sort(ver + 1, ver + 1 + N);
        FOR(i, 1, N){
            val[0][i] = lower_bound(md + 1, md + 1 + N, p[i].x - p[i].y) - md;
            val[1][i] = lower_bound(sd + 1, sd + 1 + N, p[i].x + p[i].y) - sd;
            val[2][i] = lower_bound(hor + 1, hor + 1 + N, p[i].y) - hor;
            val[3][i] = lower_bound(ver + 1, ver + 1 + N, p[i].x) - ver;
        }
        make_List('S', 'W', 0, true);
        make_List('W', 'N', 1, true);
        make_List('N', 'E', 0, true);
        make_List('E', 'S', 1, true);
        make_List('E', 'W', 2, false);
        make_List('S', 'N', 3, false);
        FOR(i, 1, N)del[i] = INF;
        del[0] = 0;
        while(!Q.empty()){
            auto[k, f, s, dir1, dir2] = Q.top();
            Q.pop();
            if(del[f] <= k && del[s] <= k)continue;
            if(del[f] <= k){
                assert(del[s] == INF);
                while(del[s] == INF) s = nxt[dir2][s];
                if(s) Q.push({p[s].intersect(p[f]), f, s, dir1, dir2});
                continue;
            }
            if(del[s] <= k){
                assert(del[f] == INF);
                while(del[f] == INF) f = nxt[dir1][f];
                if(f) Q.push({p[f].intersect(p[s]), f, s, dir1, dir2});
                continue;
            }
            del[f] = del[s] = k;
        }
        FOR(i, 1, N){
            if(del[i] == INF)cout << i << '\n';
        }
    }
}
void solve(){
    cin >> N;
    int x, y;
    char d;
    FOR(i, 1, N){
        cin >> x >> y >> d;
        p[i] = {x, y, d};
    }
    if(subtask12345 :: check()) return subtask12345 :: solve();
    if(subtask6 :: check()) return subtask6 :: solve();
    return subtask7 :: solve();
}
int main(){
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void subtask7::make_List(char, char, int, bool)':
Main.cpp:234:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |                 for(int j = 0; j < v[i].size(); ++j){
      |                                ~~^~~~~~~~~~~~~
Main.cpp:250:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |                     for(int j = 0; j < v[i].size(); ++j){
      |                                    ~~^~~~~~~~~~~~~
Main.cpp:264:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |                     for(int j = 0; j < v[i].size(); ++j){
      |                                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:343:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  343 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:344:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  344 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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