Submission #618747

#	Time	Username	Problem	Language	Result	Execution time	Memory
618747		erray	Triangles (CEOI18_tri)	C++14	20 / 100	1 ms	244 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(37);

int main() {
  int N = get_n(); //init is here
  auto Ask = [&](int a, int b, int c) {
    return is_clockwise(a + 1, b + 1, c + 1);
  };
  
  int pivot = 0;
  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);
  auto Solve = [&](bool push) {
    vector<int> st;  
    if (push) {
	  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);
    }
    if (push) {
	  bool ok = true;
	  for (int i = 0; i < N; ++i) {
	    if (i != st[0] && i != st[1]) {
		  ok &= Ask(st[0], st[1], i);
	    }
	  }
	  if (!ok) {
	    return -1;
	  }
	}
	return int(st.size());
   };
   int ans = Solve(true);
   if (ans < 0) {
     ans = Solve(false);
   }  
   cout << ans << '\n';
}

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