제출 #828582

#제출 시각아이디문제언어결과실행 시간메모리
828582MadokaMagicaFanTriangles (CEOI18_tri)C++14
100 / 100
256 ms2216 KiB
#include "bits/stdc++.h" #include "trilib.h" using namespace std; #define sz(v) ((int)v.size()) #define pb push_back #define chk is_clockwise #define indx(j) ((j + sz(ch)) % sz(ch)) void rem(vector<int> &c, int i) { for (int j = i+1; j < sz(c); ++j) c[j-1] = c[j]; c.pop_back(); } void ins(vector<int> &c, int i, int x) { c.pb(0); for (int j = sz(c) -1; j >i; --j) c[j] = c[j-1]; c[i] = x; } int main() { int n = get_n(); vector<int> ch = {1, 2, 3}; if (!chk(1,2,3)) swap(ch[1], ch[2]); for (int j = 4; j <= n; ++j) { int l = 1, r = sz(ch); assert(sz(ch) >=3); while (l < r) { int m = (l+r)/2; if (chk(ch[0], j, ch[m])) r = m; else l = m+1; } if (l > 1 && l != sz(ch)) { if (chk(ch[0], ch[l-1], j) && chk(ch[l-1], ch[l], j) && chk(ch[l], ch[0], j)) continue; } ins(ch, l, j); while (chk(ch[indx(l-2)], ch[l], ch[indx(l-1)])) { int u = indx(l-1); rem(ch, u); if (u < l) --l; } while (chk(ch[indx(l+1)], ch[l], ch[indx(l+2)])) { int u = indx(l+1); rem(ch, u); if (u < l) --l; } } give_answer(sz(ch)); }
#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...