Submission #1080885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080885		someone	Naval battle (CEOI24_battle)	C++14	100 / 100	1039 ms	90336 KiB

Main

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

const int N = 2e5 + 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};
int corr[4][8] = {{0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 1, 0, 1, 0, 1, 0, 1},
                  {1, 0, 1, 1, 1, 0, 1, 1},
                  {1, 1, 1, 0, 1, 1, 1, 0}};

Point pt[N];
bool mort[N], bourr[N];
int n, nxt[N][8];

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 != b && 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) {
    if(mort[i]) return;
    mort[i] = true;
    for(int iDir = 0; iDir < 8; iDir++) {
        for(int t = 0; t < 4; t++) if(nxt[i][iDir] != -1) {
            nxt[nxt[i][iDir]][iDir ^ 4] = nxt[i][iDir ^ 4];
            int a = nxt[i][iDir], b = nxt[i][iDir ^ 4];
            create(a, b);
        }
    }
}

void init() {
    for(int i = 0; i < n; i++)
        mort[i] = false;
    for(int i = 0; i < n; i++)
        for(int iDir = 0; iDir < 8; iDir++)
            nxt[i][iDir] = -1;
}

void readInput() {
    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];
    }
}

void solve() {
    readInput();
    init();
    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[2];
        for(int i = 0; i < n; i++) {
            int proj = pt[i].x * dirl[iDir] + pt[i].y * dirc[iDir];
            if(pre[corr[pt[i].type][iDir]].count(proj)) {
                nxt[pt[i].i][iDir] = pre[corr[pt[i].type][iDir]][proj];
                pot.push_back({pt[i].i, nxt[pt[i].i][iDir]});
            }
            pre[corr[pt[i].type][iDir]][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 << ' ';
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
}

Compilation message (stderr)

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

• 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