# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100939 | 2019-03-15T10:44:25 Z | E869120 | The Forest of Fangorn (CEOI14_fangorn) | C++14 | 700 ms | 32632 KB |
#include <iostream> #include <vector> #include <algorithm> using namespace std; #pragma warning (disable: 4996) struct Point { int px, py; }; int shogen(Point p1) { if (p1.py >= 0) return 1; return 2; } bool operator<(const Point &a1, const Point &a2) { int v1 = shogen(a1), v2 = shogen(a2); if (v1 < v2) return true; if (v1 > v2) return false; if (1LL * a1.px*a2.py > 1LL * a1.py*a2.px) return true; return false; } vector<Point>V[2009]; int H, W, sx, sy, N, C, ex[10009], ey[10009]; vector<int>vec; Point G[2009]; bool solve(int cx, int cy, int ty) { for (int i = 1; i <= N; i++) { int pos1 = -1; Point E = Point{ cx - G[i].px, cy - G[i].py }; for (int j = 0; j < 11; j++) { if (V[i][pos1 + (1 << j)] < E) pos1 += (1 << j); } pos1++; if (pos1 == N - 1) pos1 = 0; if (ty == 1 && vec[i - 1] != pos1) return false; if (ty == 0) vec.push_back(pos1); } return true; } int main() { scanf("%d%d%d%d%d", &H, &W, &sx, &sy, &C); for (int i = 1; i <= C; i++) scanf("%d%d", &ex[i], &ey[i]); scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d%d", &G[i].px, &G[i].py); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == j) continue; V[i].push_back(Point{ G[i].px - G[j].px, G[i].py - G[j].py }); } sort(V[i].begin(), V[i].end()); for (int j = 0; j < 2048 - N; j++) V[i].push_back(Point{ 1000000007LL, -1LL }); } solve(sx, sy, 0); vector<int>res; for (int i = 1; i <= C; i++) { bool vec2 = solve(ex[i], ey[i], 1); if (vec2 == true) res.push_back(i); } printf("%d\n", (int)res.size()); for (int i = 0; i < res.size(); i++) { if (i) printf(" "); printf("%d", res[i]); } if (res.size() != 0) printf("\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Incorrect | 2 ms | 512 KB | Output isn't correct |
4 | Incorrect | 2 ms | 640 KB | Output isn't correct |
5 | Incorrect | 3 ms | 512 KB | Output isn't correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Incorrect | 4 ms | 1536 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1052 KB | Output is correct |
2 | Correct | 3 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1536 KB | Output is correct |
4 | Correct | 6 ms | 1664 KB | Output is correct |
5 | Correct | 5 ms | 1664 KB | Output is correct |
6 | Correct | 7 ms | 2560 KB | Output is correct |
7 | Incorrect | 3 ms | 512 KB | Output isn't correct |
8 | Incorrect | 3 ms | 640 KB | Output isn't correct |
9 | Incorrect | 4 ms | 1408 KB | Output isn't correct |
10 | Incorrect | 9 ms | 3328 KB | Output isn't correct |
11 | Incorrect | 15 ms | 3584 KB | Output isn't correct |
12 | Correct | 8 ms | 3584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
2 | Incorrect | 2 ms | 896 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 700 ms | 32632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |