oj.uz

Submission #332531

# Submission time Handle Problem Language Result Execution time Memory
332531 2020-12-02T19:30:34 Z dolphingarlic The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 2492 ms 876 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct Point {
    int x, y, id;
} trees[2001], camps[10001], gimli, pivot;

Point operator-(Point A, Point B) { return {A.x - B.x, A.y - B.y, A.id}; }

bool operator<(Point A, Point B) {
    return copysign(1. - A.x / (fabs(A.x) + fabs(A.y)), A.y) <
           copysign(1. - B.x / (fabs(B.x) + fabs(B.y)), B.y);
}

bool good[10001];
deque<Point> sweep;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    cin >> gimli.x >> gimli.y;
    gimli.id = -1;
    int c;
    cin >> c;
    for (int i = 1; i <= c; i++) {
        cin >> camps[i].x >> camps[i].y;
        camps[i].id = i;
        good[i] = true;
    }
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) cin >> trees[i].x >> trees[i].y;
    srand(69420);
    random_shuffle(trees + 1, trees + t + 1);

    for (int i = 1; i <= t; i++) {
        pivot = trees[i];
        sweep.clear();
        sweep.push_back(gimli - pivot);
        for (int j = 1; j <= c; j++)
            if (good[j]) {
                good[j] = false;
                sweep.push_back(camps[j] - pivot);
            }
        for (int j = 1; j <= t; j++)
            if (i != j) sweep.push_back(pivot - trees[j]);
        sort(sweep.begin(), sweep.end());
        while (~sweep.front().id) {
            sweep.push_back(sweep.front());
            sweep.pop_front();
        }
        sweep.pop_front();
        for (Point j : sweep) {
            if (!j.id) break;
            good[j.id] = true;
        }
        reverse(sweep.begin(), sweep.end());
        for (Point j : sweep) {
            if (!j.id) break;
            good[j.id] = true;
        }
        if (accumulate(good + 1, good + c + 1, 0) > 5000) i++;
    }

    cout << accumulate(good + 1, good + c + 1, 0) << '\n';
    for (int i = 1; i <= c; i++)
        if (good[i]) cout << i << ' ';
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 202 ms 492 KB Output is correct
5 Correct 43 ms 384 KB Output is correct
6 Correct 886 ms 488 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1410 ms 620 KB Output is correct
2 Correct 2492 ms 844 KB Output is correct
3 Correct 907 ms 876 KB Output is correct
4 Correct 906 ms 876 KB Output is correct