Submission #960560

#	Time	Username	Problem	Language	Result	Execution time	Memory
960560		vjudge1	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	600 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());
   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());
   auto pos=find(v.begin(), v.end(), v[1]);
   vector<int> v1(v.begin(), pos+1);
   vector<int> v2(pos+1, v.end());
   vector<int> color(v1.size(), 0);
   int sum=0;
   for (int i:v2){
      if (sum<2){
         while ((int)v1.size()>=2 && is_clockwise(v1.end()[-2], v1.end()[-1], i)) v1.pop_back(), sum-=color.back(), color.pop_back();
      }
      v1.push_back(i);
      color.push_back(1);
      ++sum;
   }
   v2=vector<int>(v1.end()-sum, v1.end());
   v1.resize((int)v1.size()-sum);
   v1.swap(v2);
   color=vector<int>(v1.size(), 0);
   sum=0;
   for (int i:v2){
      if (sum<2){
         while ((int)v1.size()>=2 && is_clockwise(v1.end()[-2], v1.end()[-1], i)) v1.pop_back(), sum-=color.back(), color.pop_back();
      }
      v1.push_back(i);
      color.push_back(1);
      ++sum;
   }
   give_answer(v1.size());
   return 0;
}

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