Submission #1192939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192939		phawinbot	Naval battle (CEOI24_battle)	C++20	100 / 100	1179 ms	97668 KiB

Main

// Naval Battle
// CEOI 2024 Day 1
// 100 points submission

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;

#define x first
#define y second

int n;
P pos[202020];
char d[202020];

const int NEVER = 1999999999 + 7;

bool gone[202020];


vector<set<P>> enemyCollection;

int getNewSet() {
    int z = enemyCollection.size();
    enemyCollection.push_back(set<P>());
    return z;
}

int crashCheckLow(int pos, int sid) {
    // fprintf(stderr, "  Opponent Set: %d\n", sid);
    while(!enemyCollection[sid].empty()) {
        auto it = enemyCollection[sid].lower_bound({pos, -1});
        if(it == enemyCollection[sid].begin()) return NEVER;
        it--;
        int idx = (*it).second;
        if(gone[idx]) {
            enemyCollection[sid].erase(it);
        } else {
            return pos - (*it).first;
        }
    }
    return NEVER;
}

int crashCheckHigh(int pos, int sid) {
    // fprintf(stderr, "  Opponent Set: %d\n", sid);
    while(!enemyCollection[sid].empty()) {
        auto it = enemyCollection[sid].upper_bound({pos, 303030});
        if(it == enemyCollection[sid].end()) return NEVER;
        int idx = (*it).second;
        if(gone[idx]) {
            enemyCollection[sid].erase(it);
        } else {
            return (*it).first - pos;
        }
    }
    return NEVER;
}

class OpponentInfo {
public:
    int myPos;
    char myTeam;
    int sid;

    OpponentInfo() {}
};



vector<OpponentInfo> opponents[202020];

int getCrashTime(int idx) {
    int earliest = NEVER;
    for(OpponentInfo O: opponents[idx]) {
        // fprintf(stderr, "Check Crash Time of ship %d\n", idx + 1);
        int thisRound = NEVER;
        if(O.myTeam == 'L') {
            thisRound = crashCheckHigh(O.myPos, O.sid);
        } else {
            thisRound = crashCheckLow(O.myPos, O.sid);
        }
        earliest = min(earliest, thisRound);
    }
    return earliest;
}

priority_queue<P> ICU;
int nextEvent[202020];



void preProcessSUM(const vector<P> &ships) {
    if(ships.size() <= 1) return;
    const int NORTH_SET = getNewSet();
    const int SOUTH_SET = getNewSet();
    const int WEST_SET = getNewSet();
    const int EAST_SET = getNewSet();

    int z = ships.size();
    for(int i = 0; i < z; i++) {
        int idx = ships[i].second;
        int pos = ships[i].first;
        OpponentInfo info;
        info.myPos = pos;
        if(d[idx] == 'N') {
            enemyCollection[NORTH_SET].insert({pos, idx});
            info.sid = WEST_SET;
            info.myTeam = 'L';
        } else if(d[idx] == 'W') {
            enemyCollection[WEST_SET].insert({pos, idx});
            info.sid = NORTH_SET;
            info.myTeam = 'R';
            ////
        } else if(d[idx] == 'S') {
            enemyCollection[SOUTH_SET].insert({pos, idx});
            info.sid = EAST_SET;
            info.myTeam = 'R';
        } else if(d[idx] == 'E') {
            enemyCollection[EAST_SET].insert({pos, idx});
            info.sid = SOUTH_SET;
            info.myTeam = 'L';
        }

        opponents[idx].push_back(info); 
    }
}

void preProcessDIFF(const vector<P> &ships) {
    if(ships.size() <= 1) return;
    const int NORTH_SET = getNewSet();
    const int SOUTH_SET = getNewSet();
    const int WEST_SET = getNewSet();
    const int EAST_SET = getNewSet();

    int z = ships.size();
    // fprintf(stderr, "%d ships to consider\n", z);
    for(int i = 0; i < z; i++) {
        int idx = ships[i].second;
        int pos = ships[i].first;
        OpponentInfo info;
        info.myPos = pos;
        if(d[idx] == 'N') {
            enemyCollection[NORTH_SET].insert({pos, idx});
            info.sid = EAST_SET;
            info.myTeam = 'R';
        } else if(d[idx] == 'E') {
            enemyCollection[EAST_SET].insert({pos, idx});
            info.sid = NORTH_SET;
            info.myTeam = 'L';
            ////
        } else if(d[idx] == 'W') {
            enemyCollection[WEST_SET].insert({pos, idx});
            info.sid = SOUTH_SET;
            info.myTeam = 'R';
        } else if(d[idx] == 'S') {
            enemyCollection[SOUTH_SET].insert({pos, idx});
            info.sid = WEST_SET;
            info.myTeam = 'L';
        }

        opponents[idx].push_back(info); 
    }
}

void preProcessLine(const vector<P> &ships) {
    if(ships.size() <= 1) return;
    const int LOW_SET = getNewSet();
    const int HIGH_SET = getNewSet();

    int z = ships.size();
    // fprintf(stderr, "%d ships to consider\n", z);
    for(int i = 0; i < z; i++) {
        int idx = ships[i].second;
        int pos = ships[i].first;
        // fprintf(stderr, "(Ship %d, Pos = %d)\n", idx + 1, pos);
        OpponentInfo info;
        info.myPos = pos / 2;
        
        if(d[idx] == 'S' || d[idx] == 'E') {
            // increase coordinate by 1 (team LOW)
            enemyCollection[LOW_SET].insert({pos / 2, idx});
            info.myTeam = 'L';
            info.sid = HIGH_SET;
        } else if(d[idx] == 'N' || d[idx] == 'W') {
            // decrease coordinate by 1 (team HIGH)
            enemyCollection[HIGH_SET].insert({pos / 2, idx});
            info.myTeam = 'R';
            info.sid = LOW_SET;
        }

        opponents[idx].push_back(info);
    }
}


void processEvent(const int t) {
    // {{ Event on top of ICU is actually going to happen at time t }}
    set<int> eliminated;

    while(!ICU.empty()) {
        int claim = -ICU.top().first;
        int idx = ICU.top().second;
        if(claim != t) break;

        ICU.pop();

        int actual = getCrashTime(idx);
        if(actual == t) {
            // Yes!
            eliminated.insert(idx);
        } else {
            if(actual < NEVER) {
                ICU.push({-actual, idx});
            }
        }
    }

    for(int u: eliminated) gone[u] = true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> pos[i].x >> pos[i].y;
        string s; cin >> s;
        d[i] = s[0];

        // fprintf(stderr, "Registered Ship %d at (%d, %d) [%c]\n", i + 1, pos[i].x, pos[i].y, d[i]);
    }


    // Prepare Initial Crash
    map<int, vector<P>> sumBank, diffBank, xBank, yBank;
    for(int i = 0; i < n; i++) {
        sumBank[pos[i].x + pos[i].y].push_back({pos[i].x, i});
        diffBank[pos[i].x - pos[i].y].push_back({pos[i].x, i});
        if(d[i] == 'N' || d[i] == 'S') xBank[pos[i].x].push_back({pos[i].y, i});
        if(d[i] == 'E' || d[i] == 'W') yBank[pos[i].y].push_back({pos[i].x, i});
    }

    for(auto it = sumBank.begin(); it != sumBank.end(); it++) preProcessSUM(it->second);
    for(auto it = diffBank.begin(); it != diffBank.end(); it++) preProcessDIFF(it->second);
    for(auto it = xBank.begin(); it != xBank.end(); it++) preProcessLine(it->second);
    for(auto it = yBank.begin(); it != yBank.end(); it++) preProcessLine(it->second);


    // Start the Battle
    for(int i = 0; i < n; i++) {
        nextEvent[i] = getCrashTime(i);
        if(nextEvent[i] < NEVER) {
            ICU.push({-nextEvent[i], i});
        }
        // fprintf(stderr, "Preliminary[Ship %d]: crash at t = %d\n", i + 1, nextEvent[i]);
    }

    while(!ICU.empty()) {
        int claim = -ICU.top().first;
        int idx = ICU.top().second;
        
        // Re-Evaluation
        int actual = getCrashTime(idx);
        if(actual == claim) {
            processEvent(actual);
        } else {
            ICU.pop();
            if(actual < NEVER) {
                ICU.push({-actual, idx});
            }
        }

    }

    // Final Answer
    for(int i = 0; i < n; i++) if(!gone[i]) 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: 24 / 24