# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
667821 | 2022-12-02T06:07:48 Z | RambaXGorilla | The Forest of Fangorn (CEOI14_fangorn) | C++17 | 2272 ms | 32092 KB |
#include<cstdio> #include<algorithm> #include<utility> #include<vector> using namespace std; typedef long long ll; typedef pair <int,int> ii; int N, C, W, H; ii gimli; ii camps[10010]; ii trees[2010]; ii rays[2010][2010]; vector <int> reach; ii sub(ii a, ii b) {return ii(a.first - b.first, a.second - b.second);} bool comp(ii a, ii b){ int c = a.first + (!a.first) * a.second; int d = b.first + (!b.first) * b.second; if(!c) return false; if(!d) return true; if(c < 0 && d > 0) return false; if(d < 0 && c > 0) return true; return (ll) a.second * b.first > (ll) b.second * a.first; } int search(int j, ii a){ return (upper_bound(rays[j], rays[j] + N - 1, a, comp) - rays[j]) % (N - 1); } int main(){ scanf("%d%d%d%d",&W,&H,&gimli.first,&gimli.second); scanf("%d",&C); for(int i = 0;i < C;i++){ scanf("%d%d",&camps[i].first,&camps[i].second); } scanf("%d",&N); for(int i = 0;i < N;i++){ scanf("%d%d",&trees[i].first,&trees[i].second); } for(int i = 0;i < N;i++){ for(int j = 0;j < N;j++){ rays[i][j] = sub(trees[i], trees[j]); } sort(rays[i], rays[i] + N, comp); } for(int i = 0;i < C;i++){ bool poss = true; for(int j = 0;j < N;j++){ if(search(j, sub(gimli, trees[j])) != search(j, sub(camps[i], trees[j]))){ poss = false; break; } } if(poss) reach.push_back(i + 1); } printf("%d\n",reach.size()); for(auto i : reach){ printf("%d ",i); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 552 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 1 ms | 596 KB | Output is correct |
5 | Correct | 1 ms | 596 KB | Output is correct |
6 | Correct | 2 ms | 852 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 4 ms | 1236 KB | Output is correct |
11 | Correct | 4 ms | 1364 KB | Output is correct |
12 | Correct | 4 ms | 1320 KB | Output is correct |
# | 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 | 1 ms | 352 KB | Output is correct |
4 | Correct | 95 ms | 12088 KB | Output is correct |
5 | Correct | 24 ms | 3872 KB | Output is correct |
6 | Correct | 392 ms | 31788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 682 ms | 31896 KB | Output is correct |
2 | Correct | 2272 ms | 32092 KB | Output is correct |
3 | Correct | 422 ms | 31896 KB | Output is correct |
4 | Correct | 1617 ms | 31984 KB | Output is correct |