Submission #960565

#	Time	Username	Problem	Language	Result	Execution time	Memory
960565		vjudge1	Triangles (CEOI18_tri)	C++14	100 / 100	19 ms	2956 KiB

tri

#include "trilib.h"

#include<bits/stdc++.h>

using namespace std;

int n;

vector<int> convex_hull(vector<int> v){
   vector<int> v2;
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   return v2;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   n=get_n();
   vector<int> v(n);
   iota(v.begin(), v.end(), 1);
   vector<vector<int>> vv(2);
   for (int i=2; i<n; ++i) vv[is_clockwise(v[0], v[1], v[i])].push_back(v[i]);
   vv[0].push_back(v[1]);
   vv[1].push_back(v[1]);
   auto cmp=[&](int x, int y){
      return !is_clockwise(v[0], x, y);
   };
   function<void(vector<int> &)> merge_sort=[&](vector<int> &v) -> void {
      if ((int)v.size()<=1) return;
      vector<int> vl(v.begin(), v.begin()+(int)v.size()/2);
      vector<int> vr(v.begin()+(int)v.size()/2, v.end());
      merge_sort(vl);
      merge_sort(vr);
      merge(vl.begin(), vl.end(), vr.begin(), vr.end(), v.begin(), cmp);
   };
   merge_sort(vv[0]);
   merge_sort(vv[1]);
   vv[0].insert(vv[0].begin(), v[0]);
   vv[1].insert(vv[1].begin(), v[0]);
   vv[0]=convex_hull(vv[0]);
   vv[1]=convex_hull(vv[1]);
   bool rev=0;
   if (vv[0].back()!=v[1]) reverse(vv[0].begin()+1, vv[0].end()), rev=1;
   if (vv[1].back()!=v[1]) reverse(vv[1].begin()+1, vv[0].end());
   else rev=1;
   v.swap(vv[0]);
   v.insert(v.end(), vv[1].rbegin()+1, vv[1].rend()-1);
   if (rev) reverse(v.begin()+1, v.end());
   vector<int> v2;
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   vector<int> cnt(n+1);
   for (int i:v2) ++cnt[i];
   while (cnt[v2.back()]==1) v2.pop_back();
   reverse(v2.begin(), v2.end());
   while (cnt[v2.back()]==1) v2.pop_back();
   give_answer((int)v2.size()/2);
   return 0;
}

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