제출 #618857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618857		erray	Triangles (CEOI18_tri)	C++14	35 / 100	93 ms	440 KiB

tri

// author: erray
#include <bits/stdc++.h>

#include "trilib.h"

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/debug.h"
#else
  #define debug(...) void(37)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int N;
int Ask(int a, int b, int c) {
  return is_clockwise(a + 1, b + 1, c + 1);
}
	
int back = -1;
int solve(int pivot) {
  function<vector<int>(vector<int>)> Dfs = [&](vector<int> p) {
    int s = int(p.size());
    if (s < 2) {
	  return p;
	}
    int mid = uniform_int_distribution<int>(0, s - 1)(rng);
    array<vector<int>, 2> split;
    for (int i = 0; i < s; ++i) {
	  if (i != mid) {
	    split[Ask(pivot, p[mid], p[i])].push_back(p[i]);
	  }
	}
	auto left = Dfs(split[0]);
	left.push_back(p[mid]);
	auto right = Dfs(split[1]);
	left.insert(left.end(), right.begin(), right.end());
	return left;
  };
  vector<int> ord(N);
  iota(ord.begin(), ord.end(), 0);
  ord.erase(ord.begin() + pivot);
  ord = Dfs(ord);

  /*
  bool pivot_convex = true;
  for (int i = 0; i < N; ++i) {
    if (i != ord.back() && i != pivot) {
	  pivot_convex &= Ask(ord.back(), pivot, i);
	}
  }
  if (pivot_convex) {
    ord.push_back(pivot);
  }
  */
  vector<int> st;
  st.push_back(pivot);
  for (auto i : ord) {
	while (int(st.size()) >= 2 && !Ask(st[int(st.size()) - 2], st.back(), i)) {
	  st.pop_back();
	}
	st.push_back(i);
  }
  back = st.back();
  return int(st.size());
}

int main() {
  N = get_n(); //init is here
  int ans = N;
  for (int i = 0; i < N; ++i) {
    ans = min(ans, solve(i));
  }
  cout << ans << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25