oj.uz

Submission #442351

# Submission time Handle Problem Language Result Execution time Memory
442351 2021-07-07T13:40:50 Z prvocislo The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 1291 ms 716 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct bod { ll x, y; };
bool up(const bod &x) { return x.x > 0 || (x.x == 0 && x.y > 0); }
bod sub(const bod &a, const bod &b) { return {a.x-b.x, a.y-b.y}; }
bool cmp(const bod &a, const bod &b) 
{
    bool ua = up(a), ub = up(b);
    if (ua ^ ub) return ua > ub;
    return a.x * b.y - a.y * b.x > 0; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int w, h, nc, nf;
    cin >> w >> h;
    bod g;
    cin >> g.x >> g.y;
    cin >> nc;
    vector<bod> c(nc);
    for (int i = 0; i < nc; i++) cin >> c[i].x >> c[i].y;
    cin >> nf;
    vector<bod> f(nf);
    for (int i = 0; i < nf; i++) cin >> f[i].x >> f[i].y;
    vector<bool> ok(nc, true);
    for (int i = 0; i < nf; i++)
    {
        vector<bod> v;
        for (int j = 0; j < nf; j++) if (i != j) v.push_back(sub(f[i], f[j]));
        sort(v.begin(), v.end(), cmp);
        int pos = (lower_bound(v.begin(), v.end(), sub(g, f[i]), cmp) - v.begin()) % v.size();
        for (int j = 0; j < nc; j++)
        {
            if (!ok[j]) continue;
            int pos2 = (lower_bound(v.begin(), v.end(), sub(c[j], f[i]), cmp) - v.begin()) % v.size();
            if (pos2 ^ pos) ok[j] = false;
        }
    }
    int sz = count(ok.begin(), ok.end(), true);
    cout << sz << "\n";
    for (int i = 0; i < nc; i++) if (ok[i]) cout << i+1 << " ";
    cout << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 107 ms 356 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 481 ms 332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 460 KB Output is correct
2 Correct 1291 ms 716 KB Output is correct
3 Correct 499 ms 716 KB Output is correct
4 Correct 782 ms 588 KB Output is correct