Submission #618980

#	Time	Username	Problem	Language	Result	Execution time	Memory
618980		erray	Triangles (CEOI18_tri)	C++14	35 / 100	41 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 query = 0;
int Ask(int a, int b, int c) {
  if (query += 1 == int(1E6) - 5) {
	assert(false);  
  }
  
  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);
  }
  
  bool convex = true;
  int s = int(st.size());
  for (int i = 0; i < s; ++i) {
    int n1 = (i + 1) % s;
    int n2 = (i + 2) % s;
    convex &= Ask(st[i], st[n1], st[n2]);
  } 
  return (convex ? s : -1);
}

int main() {
  N = get_n(); //init is here
  int ans = 0;
  do {
    ans = solve(rng() % N);
  } while (ans == -1);
  cout << ans << '\n';
}

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