Submission #1180065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180065		LucaIlie	Naval battle (CEOI24_battle)	C++20	36 / 100	900 ms	142704 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct ship {
    int x, y, dir;
};

struct candidate {
    int t, i, j;

    bool operator < ( const candidate &x ) const {
        if ( x.t == t ) {
            if ( x.i == i )
                return j < x.j;
            return i < x.i;
        }
        return t < x.t;
    }
};

const int MAX_N = 2e5;
const int N = 0;
const int S = 1;
const int V = 2;
const int E = 3;
bool alive[MAX_N];
unordered_map<int, set<pair<int, int>>> se, sv, ne, nv, ve, sn;
ship ships[MAX_N];
priority_queue<candidate> cand;

void insertShip( int i ) {
    int x = ships[i].x, y = ships[i].y;
    if ( ships[i].dir == S ) {
        se[x + y].insert( { y, i } );
        sv[x - y].insert( { y, i } );
        sn[x].insert( { y, i } );
    } else if ( ships[i].dir == N ) {
        ne[x - y].insert( { y, i } );
        nv[x + y].insert( { y, i } );
        sn[x].insert( { y, i } );
    } else if ( ships[i].dir == E ) {
       se[x + y].insert( { y, i } );
       ne[x - y].insert( { y, i } );
       ve[y].insert( { x, i } );
    } else {
        sv[x - y].insert( { y, i } );
        nv[x + y].insert( { y, i } );
        ve[y].insert( { x, i } );
    }
}

void eraseShip( int i ) {
    int x = ships[i].x, y = ships[i].y;
    if ( ships[i].dir == S ) {
        se[x + y].erase( { y, i } );
        sv[x - y].erase( { y, i } );
        sn[x].erase( { y, i } );
    } else if ( ships[i].dir == N ) {
        ne[x - y].erase( { y, i } );
        nv[x + y].erase( { y, i } );
        sn[x].erase( { y, i } );
    } else if ( ships[i].dir == E ) {
        se[x + y].erase( { y, i } );
        ne[x - y].erase( { y, i } );
        ve[y].erase( { x, i } );
    } else {
        sv[x - y].erase( { y, i } );
        nv[x + y].erase( { y, i } );
        ve[y].erase( { x, i } );
    }
}

void check( int d1, int d2, set<pair<int, int>> &s, int i, int x ) {
    if ( ships[i].dir != d1 )
        return;

    if ( s.upper_bound( { x, i } ) == s.end() )
        return;

    int j = s.upper_bound( { x, i } )->second;
    if ( ships[j].dir != d2 )
        return;

    cand.push( candidate{ -(abs( ships[j].x - ships[i].x ) + abs( ships[j].y - ships[i].y )) / 2, i, j } );
}


void getCand( int i ) {
    int x = ships[i].x, y = ships[i].y;

    check( E, V, ve[y], i, x );
    check( S, N, sn[x], i, y );
    check( S, E, se[x + y], i, y );
    check( S, V, sv[x - y], i, y );
    check( E, N, ne[x - y], i, y );
    check( V, N, nv[x + y], i, y );
}

void refresh( int d1, int d2, set<pair<int, int>> &s, int i, int x ) {
    if ( ships[i].dir != d1 )
        return;

    if ( s.upper_bound( { x, i } ) == s.begin() )
        return;

    auto p = s.upper_bound( { x, i } );
    p--;
    int j = p->second;

    check( d1, d2, s, j, x );
}

void refreshCand( int i ) {
    int x = ships[i].x, y = ships[i].y;

    refresh( E, V, ve[y], i, x );
    refresh( S, N, sn[x], i, y );
    refresh( S, E, se[x + y], i, y );
    refresh( S, V, sv[x - y], i, y );
    refresh( E, N, ne[x - y], i, y );
    refresh( V, N, nv[x + y], i, y );
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        char dir;
        cin >> ships[i].x >> ships[i].y >> dir;
        ships[i].dir = (dir == 'N' ? N : (dir == 'S' ? S : (dir == 'E' ? E : V)));
        insertShip( i );
        alive[i] = true;
    }

    for ( int i = 0; i < n; i++ ) 
        getCand( i );

    //cout << "START " << cand.size() << "\n";
    //for ( auto c: cand )
    //    cout << c.t << " " << c.i << " " << c.j << "\n";
    while ( !cand.empty() ) {
        candidate c = cand.top();

        if ( !alive[c.i] || !alive[c.j] ) {
            cand.pop();
            continue;
        }

        vector<int> deadShips;
        while ( !cand.empty() && cand.top().t == c.t ) {
            c = cand.top();
            cand.pop();
            if ( !alive[c.i] || !alive[c.j] ) 
                continue;

            deadShips.push_back( c.i );
            deadShips.push_back( c.j );
        }

        sort( deadShips.begin(), deadShips.end() );
        deadShips.resize( unique( deadShips.begin(), deadShips.end() ) - deadShips.begin() );

        for ( int i: deadShips ) {
            alive[i] = false;
            eraseShip( i );
        }
        for ( int i: deadShips )
            refreshCand( i );
    }

    //cout << "FINISH\n";
    for ( int i = 0; i < n; i++ ) {
        if ( alive[i] )
            cout << i + 1 << "\n";
    }   

    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