Submission #1265748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265748		Lobo	Naval battle (CEOI24_battle)	C++20	6 / 100	166 ms	48484 KiB

Main

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define fr first
#define sc second

const int maxn = 1e5+10;
const int inf = 1e9;

int H, L, n, x[maxn], y[maxn], block[maxn];
int xc[maxn], yc[maxn], tc[maxn];
char d[maxn];
priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;

map<int,set<pair<int,int>>> pos[10];

char di[10], dj[10];

int dist2(int tp, int i, int j) {
    if(tp <= 3) {
        return 2*abs(x[i]-x[j]);
    }
    else if(tp == 4) {
        return abs(x[i]-x[j]);
    }
    else if (tp == 5){
        return abs(y[i]-y[j]);
    }
    else if(tp <= 7) {
        return 2*abs(x[i]-xc[j]);
    }
    else {
        return 2*abs(y[i]-yc[j]);
    }
}

int cntcol;
void addcol(int X, int Y, int T) {
    xc[cntcol] = X;
    yc[cntcol] = Y;
    tc[cntcol] = T;

    for(int tp = 6; tp <= 9; tp++) {
        if(tp == 6 or tp == 8) {
            auto it = pos[tp][(tp == 6 ? Y : X)].upper_bound({(tp == 6 ? X : Y)-T,inf});

            if(it != pos[tp][(tp == 6 ? Y : X)].begin()) {
                int i = prev(it)->sc;
                pq.push({dist2(tp,i,cntcol),i,cntcol,tp});
            }
        }
        else {
            auto it = pos[tp][(tp == 7 ? Y : X)].upper_bound({(tp == 7 ? X : Y)+T,-inf});
            if(it != pos[tp][(tp == 7 ? Y : X)].end()) {
                int i = it->sc;
                pq.push({dist2(tp,i,cntcol),i,cntcol,tp});
            }
        }
    }
    cntcol++;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    di[0] = 'N';
    dj[0] = 'W';
    di[1] = 'E';
    dj[1] = 'S';
    di[2] = 'E';
    dj[2] = 'N';
    di[3] = 'S';
    dj[3] = 'W';
    di[4] = 'E';
    dj[4] = 'W';
    di[5] = 'S';
    dj[5] = 'N';
    di[6] = 'E';
    dj[6] = 'X';
    di[7] = 'W';
    dj[7] = 'X';
    di[8] = 'S';
    dj[8] = 'X';
    di[9] = 'N';
    dj[9] = 'X';

    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> d[i];

        if(d[i] == 'N') {
            pos[0][x[i]+y[i]].insert({x[i],i});
            pos[2][x[i]-y[i]].insert({x[i],i});
            pos[5][x[i]].insert({y[i],i});
            pos[9][x[i]].insert({y[i],i});
        }

        if(d[i] == 'W') {
            pos[0][x[i]+y[i]].insert({x[i],i});
            pos[3][x[i]-y[i]].insert({x[i],i});
            pos[4][y[i]].insert({x[i],i});
            pos[7][y[i]].insert({x[i],i});
        }

        if(d[i] == 'E') {
            pos[1][x[i]+y[i]].insert({x[i],i});
            pos[2][x[i]-y[i]].insert({x[i],i});
            pos[4][y[i]].insert({x[i],i});
            pos[6][y[i]].insert({x[i],i});
        }

        if(d[i] == 'S') {
            pos[1][x[i]+y[i]].insert({x[i],i});
            pos[3][x[i]-y[i]].insert({x[i],i});
            pos[5][x[i]].insert({y[i],i});
            pos[8][x[i]].insert({y[i],i});
        }
    }

    for(int tp = 0; tp <= 5; tp++) {
        int LL,R;
        for(auto X : pos[tp]) {
            int v = X.fr;
            if(pos[tp][v].size() == 0) continue;
            auto it = pos[tp][v].begin();

            while(next(it) != pos[tp][v].end()) {
                int i = it->sc;
                it++;
                int j = it->sc;

                if(d[i] == di[tp] and d[j] == dj[tp]) {
                    pq.push({dist2(tp,i,j),i,j,tp});
                }
            }
        }
    }


    while(pq.size()) {
        int i = pq.top()[1];
        int j = pq.top()[2];
        int tp = pq.top()[3];
        pq.pop();

        int qual;

        if(tp == 0) {
            qual = x[i]+y[i];
        }
        else if(tp == 1) {
            qual = x[i]+y[i];
        }
        else if(tp == 2) {
            qual = x[i]-y[i];
        }
        else if(tp == 3) {
            qual = x[i]-y[i];
        }
        else if(tp == 4) {
            qual = y[i];
        }
        else if(tp == 5) {
            qual = x[i];
        }
        else if(tp == 6) {
            qual = y[i];
        }
        else if(tp == 7) {
            qual = y[i];
        }
        else if(tp == 8) {
            qual = x[i];
        }
        else if(tp == 9) {
            qual = x[i];
        }

        if(block[i]) {
            auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});

            if(it == pos[tp][qual].end()) {continue;}

            if(tp == 7 or tp == 9) {
                if(next(it) != pos[tp][qual].end()) {
                    int i1 = next(it)->sc;
                    if(d[i1] == di[tp]) {
                        pq.push({dist2(tp,i1,j),i1,j,tp});
                    }
                }
            }
            else {
                if(it != pos[tp][qual].begin()) {
                    int i1 = prev(it)->sc;
                    if(d[i1] == di[tp]) {
                        pq.push({dist2(tp,i1,j),i1,j,tp});
                    }
                }
            }
            pos[tp][qual].erase(it);
        }
        else if(tp <= 5 and block[j]) {
            auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[j] : x[j]),j});
            if(it == pos[tp][qual].end()) {continue;}

            if(next(it) != pos[tp][qual].end()) {
                int j1 = next(it)->sc;
                if(d[j1] == dj[tp]) {
                    pq.push({dist2(tp,i,j1),i,j1,tp});
                }
            }
            pos[tp][qual].erase(it);
        }
        else if(tp <= 5) {
            block[i] = 1;
            block[j] = 1;

            auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});

            int i1 = -1;
            if(it != pos[tp][qual].begin()) {
                i1 = prev(it)->sc;
            }

            it++;
            int j1 = -1;
            if(next(it) != pos[tp][qual].end()) {
                j1 = next(it)->sc;
            }

            pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
            pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[j] : x[j]),j});

            if(i1 != -1 and j1 != -1 and d[i1] == di[tp] and d[j1] == dj[tp]) {
                pq.push({dist2(tp,i1,j1),i1,j1,tp});
            }

            // colocar essa colisao em 6 7 8 9

            // if(tp == 0 or tp == 3) {
            //     addcol(x[i],y[j],abs(x[i]-x[j]));
            // }
            // else if(tp == 1 or tp == 2) {
            //     addcol(x[j],y[i],abs(x[i]-x[j]));
            // }
            // else if(tp == 4) {
            //     addcol((x[i]+x[j]+1)/2,y[i],(abs(x[i]-x[j])+1)/2);
            // }
            // else {
            //     addcol(x[i],(y[i]+y[j])/2,(abs(y[i]-y[j])+1)/2);
            // }
        }
        else {
            block[i] = 1;
            auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
            
            int i1 = -1;

            if(tp == 6 or tp == 8) {                
                if(it != pos[tp][qual].begin()) {
                    i1 = prev(it)->sc;
                }
            }
            else {
                if(next(it) != pos[tp][qual].end()) {
                    i1 = next(it)->sc;
                }
            }
            
            pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});

            if(i1 != -1) {
                pq.push({dist2(tp,i1,j),i1,j,tp});
            }
        }
    }
    
    for(int i = 0; i < n; i++) {
        if(!block[i]) {
            cout << i+1 << " ";
        }
    }

}

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