제출 #990988

#제출 시각아이디문제언어결과실행 시간메모리
990988starchanTriangles (CEOI18_tri)C++17
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> #include "trilib.h" using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back /*bool is_clockwise(int i, int j, int k) { cout << "Are the vertices numbered " << i << " " << j << " " << k << " clockwise in this order?" << endl; string ret; cin >> ret; return (ret[0] == 'y' || ret[0] == 'Y'); }*/ vector<int> solve(int n) { if(n == 3) { if(is_clockwise(1, 2, 3)) return {1, 2, 3}; else return {3, 2, 1}; } vector<int> v = solve(n-1); int K = v.size(); //v[0], v[1], ..., v[] int md = is_clockwise(v[0], v[1], n); int l = 0; int r = K-1; int p = -1;//non MD element. while(l < r) { if((r-l+1) <= 6) { while((l < r) && (is_clockwise(v[l], v[(l+1)%K], n) == md)) l++; while((r > l) && (is_clockwise(v[r], v[(r+1)%K], n) == md)) r--; if((l == r) && (is_clockwise(v[l], v[(l+1)%K], n) == md)) return v; vector<int> c; c.pb(n); if(md == 1) { int u = (r+1)%K; if(l < u) l+=K; for(int t = u; t <= l; t++) c.pb(v[t%K]); return c; } else { int u = l; r = (r+1)%K; if(r < u) r+=K; for(int t = u; t <= r; t++) c.pb(v[t%K]); } return c; } int a = (2*l+r)/3; int b = (2*r+l)/3; //[l, a, b, r] if(is_clockwise(v[a], v[(a+1)%K], n) != md) { p = a; break; } if(is_clockwise(v[b], v[(b+1)%K], n) != md) { p = b; break; } l = a; r = b; } int L1 = 0; int R1 = p;//first non md. while(L1 < R1) { int m = (L1+R1)/2; if(is_clockwise(v[m], v[(m+1)%K], n) != md) R1 = m; else L1 = m+1; } int L2 = p+1; int R2 = K;//first md. while(L2 < R2) { int m = (L2+R2)/2; if(is_clockwise(v[m], v[(m+1)%K], n) == md) R2 = m; else L2 = m+1; } //L1, ..., R2 consists of non mds. if(md == 0) swap(L1, R2); //1...L1 --> n --> R2 --> vector<int> c; c.pb(n); if(L1 < R2) L1+=K; for(int j = R2; j <= L1; j++) c.pb(v[j%K]); return c; } signed main() { /*int n; cin >> n; vector<int> vv = solve(n); cout << "Convex hull = " << endl; for(auto tt: vv) cout << tt << " "; cout << endl;*/ give_answer(solve(get_n()).size()); return 0; }
#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...