Submission #1214271

#TimeUsernameProblemLanguageResultExecution timeMemory
1214271ByeWorldTriangles (CEOI18_tri)C++20
0 / 100
0 ms328 KiB
#include "trilib.h" #include <bits/stdc++.h> // #pragma GCC optimize("O3") #define ll long long #define se second #define fi first #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; typedef pair<ll,ll> pii; typedef pair<int,pii> ipii; typedef pair<pii,int> piii; const int MAXN = 1e7+10; const int SQRT = 450; const int INF = 1e9+10; const int MOD = 998244353; const int LOG = 30; int n; vector<int> up, dw, urut; bool cmp(int a, int b){ if(is_clockwise(2, a, b)) return 1; return 0; } vector<int> ANS; void solve(){ ANS.clear(); ANS.pb(urut[0]); ANS.pb(urut[1]); for(int i=2; i<urut.size(); i++){ while(ANS.size()>=2 && !is_clockwise( ANS[ANS.size()-2], ANS.back(), urut[i]) ) ANS.pop_back(); ANS.pb(urut[i]); } while(ANS.size() > 3 && !is_clockwise( ANS.back(), ANS[0], ANS[1]) ){ vector<int> vec; for(int j=1; j<ANS.size(); j++){ vec.pb(ANS[j]); } ANS = vec; } } signed main(){ n = get_n(); if(n==3){ give_answer(n); exit(0); } for(int i=3; i<=n; i++){ if(is_clockwise(1, 2, i)) dw.pb(i); else up.pb(i); } sort(dw.begin(), dw.end(), cmp); sort(up.begin(), up.end(), cmp); // for(auto in : up) cout << in << " up\n"; // for(auto in : dw) cout << in << " dw\n"; urut.pb(1); for(auto in : up) urut.pb(in); urut.pb(2); for(auto in : dw) urut.pb(in); solve(); give_answer((int)ANS.size()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...