Submission #1040799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040799		elazarkoren	Naval battle (CEOI24_battle)	C++17	0 / 100	910 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 2e5 + 5;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int mptype[200];

int x[MAX_N], y[MAX_N], type[MAX_N];

pair<int, pii> Crash(int i, int j) {
    if (type[i] == type[j]) return {-1, {}};
    if (type[i] > type[j]) swap(i, j);
    if (!type[i] && type[j] == 1) {
        if (x[i] != x[j] || y[i] > y[j] || ((y[i] ^ y[j]) & 1)) return {-1, {}};
        return {(y[j] - y[i]) / 2, {x[i], (y[i] + y[j]) / 2}};
    }
    if (!type[i] && type[j] == 2) {
        if (x[i] + y[i] != x[j] + y[j] || x[i] < x[j]) return {-1, {}};
        return {x[i] - x[j], {x[i], y[j]}};
    }
    if (!type[i] && type[j] == 3) {
        if (x[i] - y[i] != x[j] - y[j] || x[i] > x[j]) return {-1, {}};
        return {x[j] - x[i], {x[i], y[j]}};
    }
    if (type[i] == 1 && type[j] == 2) {
        if (x[i] - y[i] != x[j] - y[j] || x[i] < x[j]) return {-1, {}};
        return {x[i] - x[j], {x[i], y[j]}};
    }
    if (type[i] == 1 && type[j] == 3) {
        if (x[i] + y[i] != x[j] + y[j] || x[i] < x[j]) return {-1, {}};
        return {x[j] - x[i], {x[i], y[j]}};
    }
    if (y[i] != y[j] || x[i] > x[j] || ((x[i] ^ x[j]) & 1)) return {-1, {}};
    return {(x[j] - x[i]) / 2, {(x[i] + x[j]) / 2, y[i]}};
}

int crash_t[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    mptype['S'] = 0, mptype['N'] = 1, mptype['E'] = 2, mptype['W'] = 3;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char t;
        cin >> x[i] >> y[i] >> t;
        type[i] = mptype[t];
    }
    vector<pair<pair<int, pii>, pii>> events; //{{time, {x, y}}, {s1, s2}}
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            auto p = Crash(i, j);
            if (p.x == -1) continue;
            events.push_back({p, {i, j}});
        }
    }
    sort(all(events));
    for (auto [p, q] : events) {
        auto [t, pos] = p;
        auto [i, j] = q;
        if (crash_t[j]) swap(i, j);
        if (crash_t[j]) continue;
        if (!crash_t[i]) {
            crash_t[i] = crash_t[j] = t;
        } else if (crash_t[i] == t) {
            crash_t[j] = t;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!crash_t[i]) cout << i + 1 << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   61 |         type[i] = mptype[t];
      |                          ^

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