oj.uz

Submission #554761

# Submission time Handle Problem Language Result Execution time Memory
554761 2022-04-29T11:18:43 Z alextodoran The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 1421 ms 848 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int T_MAX = 2000;
const int C_MAX = 10000;

struct Point {
    ll x, y;
};

ll W, H;
int T, C;
Point me;
Point trees[T_MAX + 2];
Point camps[C_MAX + 2];

ld getlen (const Point &a, const Point &b) {
    ld x, y;
    if (a.y == b.y) {
        x = -1;
    } else if (a.y > b.y) {
        x = a.x + (ld) (b.x - a.x) / (b.y - a.y) * (0 - a.y);
    } else {
        x = a.x + (ld) (b.x - a.x) / (b.y - a.y) * (H - a.y);
    }
    if (a.x == b.x) {
        y = -1;
    } else if (a.x > b.x) {
        y = a.y + (ld) (b.y - a.y) / (b.x - a.x) * (0 - a.x);
    } else {
        y = a.y + (ld) (b.y - a.y) / (b.x - a.x) * (W - a.x);
    }
    if (!(0 <= x && x <= W)) {
        return (a.x < b.x ? W + y : W + H + W + (H - y));
    } else {
        return (a.y < b.y ? W + H + (W - x) : x);
    }
}

ll clen[C_MAX + 2];
int cperm[C_MAX + 2];

bool canReach[C_MAX + 2];

int tperm[T_MAX + 2];
void splitBy (int t) {
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = trees[t].x * 2 - trees[t1].x;
        trees[t1].y = trees[t].y * 2 - trees[t1].y;
    }
    iota(tperm + 1, tperm + T + 1, 1);
    swap(tperm[t], tperm[T]);
    sort(tperm + 1, tperm + (T - 1) + 1, [&] (const int &t1, const int &t2) {
        return getlen(trees[t], trees[t1]) < getlen(trees[t], trees[t2]);
    });
    int idme = 0;
    while (idme + 1 < T && getlen(trees[t], trees[tperm[idme + 1]]) < getlen(trees[t], me)) {
        idme++;
    }
    if (idme == 0) {
        idme = T - 1;
    }
    for (int ci = 1, ti = 0; ci <= C; ci++) {
        while (ti + 1 < T && getlen(trees[t], trees[tperm[ti + 1]]) < clen[cperm[ci]]) {
            ti++;
        }
        int idc = (ti > 0 ? ti : T - 1);
        if (idc != idme) {
            canReach[cperm[ci]] = false;
        }
    }
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = trees[t].x * 2 - trees[t1].x;
        trees[t1].y = trees[t].y * 2 - trees[t1].y;
    }
}

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

    cin >> W >> H;
    cin >> me.x >> me.y;
    cin >> C;
    for (int c = 1; c <= C; c++) {
        cin >> camps[c].x >> camps[c].y;
    }
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> trees[t].x >> trees[t].y;
    }

    for (int c = 1; c <= C; c++) {
        if (camps[c].y == 0) {
            clen[c] = camps[c].x;
        } else if (camps[c].x == W) {
            clen[c] = W + camps[c].y;
        } else if (camps[c].y == H) {
            clen[c] = W + H + (W - camps[c].x);
        } else {
            clen[c] = W + H + W + (H - camps[c].y);
        }
    }
    iota(cperm + 1, cperm + C + 1, 1);
    sort(cperm + 1, cperm + C + 1, [&] (const int &c1, const int &c2) {
        return clen[c1] < clen[c2];
    });

    fill(canReach + 1, canReach + C + 1, true);
    for (int t = 1; t <= T; t++) {
        splitBy(t);
    }

    vector <int> reach;
    for (int c = 1; c <= C; c++) {
        if (canReach[c] == true) {
            reach.push_back(c);
        }
    }
    cout << (int) reach.size() << "\n";
    for (int c : reach) {
        cout << c << " ";
    }
    cout << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 9 ms 348 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 9 ms 352 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 301 ms 348 KB Output is correct
5 Correct 67 ms 340 KB Output is correct
6 Correct 1165 ms 372 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 388 KB Output is correct
2 Correct 1190 ms 848 KB Output is correct
3 Correct 1421 ms 788 KB Output is correct
4 Correct 1385 ms 752 KB Output is correct