Submission #1080753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080753		someone	Naval battle (CEOI24_battle)	C++14	6 / 100	576 ms	46124 KiB

Main

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using namespace std;

const int N = 2e5 + 42, T = 18, INF = 1e9 + 42;

struct Point {
    int x, y, i, type;
};

//NSEW
int dl[] = {0, 0, 1, -1},
    dc[] = {-1, 1, 0, 0};
int dirl[] = {-2, -1, 0, 1, 2, 1, 0, -1},
    dirc[] = {0, 1, 2, 1, 0, -1, -2, -1};

Point pt[N];
bool mort[N];
int nxt[N][8][4];

struct Pair {
    int i, j, dist;

    bool operator <(const Pair& other) const {
        return dist > other.dist;
    }
};

priority_queue<Pair> pq;

void create(int a, int b) {
    if(a != -1 && b != -1 && !mort[a] && !mort[b]) {
        Point p = pt[a], q = pt[b];
        int dist = (abs(p.x - q.x) + abs(p.y - q.y))/2;
        if(p.x + dist * dl[p.type] == q.x + dist * dl[q.type] && p.y + dist * dc[p.type] == q.y + dist * dc[q.type]) {
            pq.push({a, b, dist});
        }
    }
}

void del(int i) {
    mort[i] = true;
    int type = pt[i].type;
    for(int iDir = 0; iDir < 8; iDir++) {
        for(int t = 0; t < 4; t++) if(nxt[i][iDir][t] != -1) {
            nxt[nxt[i][iDir][t]][(iDir + 4) & 7][type] = nxt[i][(iDir + 4) & 7][type];
            int a = nxt[i][iDir][t], b = nxt[i][(iDir + 4) & 7][type];
            create(a, b);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    map<char, int> cor;
    cor['N'] = 0, cor['S'] = 1, cor['E'] = 2, cor['W'] = 3;
    for(int i = 0; i < n; i++) {
        pt[i].i = i;
        cin >> pt[i].x >> pt[i].y;
        char c; cin >> c;
        pt[i].type = cor[c];
    }
    vector<pair<int, int>> pot;
    for(int iDir = 0; iDir < 8; iDir++) {
        sort(pt, pt + n,
        [=](Point a, Point b) {
            return a.x * dirc[iDir] - a.y * dirl[iDir] < b.x * dirc[iDir] - b.y * dirl[iDir];
        });

        map<int, int> pre[4];
        for(int i = 0; i < n; i++) {
            int proj = pt[i].x * dirl[iDir] + pt[i].y * dirc[iDir];
            for(int t = 0; t < 4; t++) {
                if(pre[t].count(proj)) {
                    nxt[pt[i].i][iDir][t] = pre[t][proj];
                    pot.push_back({pt[i].i, nxt[pt[i].i][iDir][t]});
                } else {
                    nxt[pt[i].i][iDir][t] = -1;
                }
            }
            pre[pt[i].type][proj] = pt[i].i;
        }
    }
    sort(pt, pt + n,
    [](Point a, Point b) {
        return a.i < b.i;
    });
    for(auto [a, b] : pot) create(a, b);

    while(!pq.empty()) {
        int dist = pq.top().dist;
        vector<int> suppr;
        while(!pq.empty() && pq.top().dist == dist) {
            int a = pq.top().i, b = pq.top().j;
            if(!mort[a] && !mort[b]) {
                suppr.push_back(a);
                suppr.push_back(b);
            }
            pq.pop();
        }
        for(int i : suppr)
            if(!mort[i])
                del(i);
    }
    for(int i = 0; i < n; i++)
        if(!mort[i]) cout << i+1 << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |     for(auto [a, b] : pot) create(a, b);
      |              ^

• 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