oj.uz

Submission #554731

# Submission time Handle Problem Language Result Execution time Memory
554731 2022-04-29T10:11:51 Z alextodoran The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 11572 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 {
    int x, y;
};

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

ld ang (const Point &a, const Point &b) {
    return atan2(b.y - a.y, b.x - a.x);
}

int id[T_MAX + 2][C_MAX + 2];
int tperm[T_MAX + 2], cperm[C_MAX + 2];
void splitBy (int t) {
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = 2 * trees[t].x - trees[t1].x;
        trees[t1].y = 2 * trees[t].y - 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 ang(trees[t], trees[t1]) < ang(trees[t], trees[t2]);
    });
    iota(cperm + 1, cperm + C + 1, 1);
    sort(cperm + 1, cperm + C + 1, [&] (const int &c1, const int &c2) {
        return ang(trees[t], camps[c1]) < ang(trees[t], camps[c2]);
    });
    for (int ci = 1, ti = 0; ci <= C; ci++) {
        while (ti + 1 < T && ang(trees[t], trees[tperm[ti + 1]]) < ang(trees[t], camps[cperm[ci]])) {
            ti++;
        }
        id[t][cperm[ci]] = (ti > 0 ? ti : T - 1);
    }
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = 2 * trees[t].x - trees[t1].x;
        trees[t1].y = 2 * trees[t].y - 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;
    }
    camps[++C] = me;

    for (int t = 1; t <= T; t++) {
        splitBy(t);
    }

    vector <int> reach;
    for (int c = 1; c < C; c++) {
        bool ok = true;
        for (int t = 1; t <= T; t++) {
            if (id[t][c] != id[t][C]) {
                ok = false;
                break;
            }
        }
        if (ok == 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 12 ms 852 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 22 ms 1036 KB Output is correct
11 Correct 20 ms 1100 KB Output is correct
12 Correct 30 ms 1100 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 760 ms 4444 KB Output is correct
5 Correct 158 ms 2256 KB Output is correct
6 Execution timed out 3091 ms 8012 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 11572 KB Time limit exceeded
2 Halted 0 ms 0 KB -