Submission #1227336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227336		madamadam3	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;

int n, m, k;
vi r, c, L, R;

void preprocess(int N, int M, int K, vi Row, vi Col) {
    set<int> points; for (int i = 0; i < N; i++) points.insert(i);
    vector<int> to_erase;

    for (int i = 0; i < N; i++) {
        if (!points.count(i)) continue;

        int Li = min(Row[i], Col[i]), Ri = max(Row[i], Col[i]);
        for (auto &el : points) {
            if (i == el) continue;
            if (Li <= Col[el] && Col[el] <= Ri && Li <= Row[el] && Row[el] <= Ri) {
                to_erase.push_back(el);
            }
        }

        for (auto &el : to_erase) {
            points.erase(el);
        }

        to_erase.clear();
    }

    vector<int> sorted_points(points.begin(), points.end());
    sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
        int La = min(Row[a], Col[a]), Ra = max(Row[a], Col[a]), Lb = min(Row[b], Col[b]), Rb = max(Row[b], Col[b]);
        return La == Lb ? Ra < Rb : La < Lb;
    });

    n = points.size(); m = M; k = K;
    r.resize(n); c.resize(n); L.resize(n); R.resize(n);
    for (int i = 0; i < n; i++) {
        r[i] = Row[sorted_points[i]]; c[i] = Col[sorted_points[i]];

        L[i] = min(r[i], c[i]);
        R[i] = max(r[i], c[i]);
    }
}

ll sub1() {
    vvi used(m, vi(m, 0));
    for (int i = 0; i < n; i++) {
        for (int x = L[i]; x <= R[i]; x++) {
            for (int y = L[i]; y <= R[i]; y++) {
                used[x][y]++;
            }
        }
    }

    ll ans = 0;
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < m; y++) {
            if (used[x][y]) ans++;
        }
    }
    return ans;
}

ll take_photos(int N, int M, int K, vi Row, vi Col) {
    preprocess(N, M, K, Row, Col);

    return sub1();
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40