Submission #1202712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202712		loom	Triangles (CEOI18_tri)	C++20	0 / 100	0 ms	328 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define inf 5e18
#define nl '\n'
 
bool cmp(int a, int b){
   return is_clockwise(1, a, b);
}

vector<int> func(vector<int>& v){
   sort(v.begin(), v.end(), cmp);
   vector<int> ans;
   ans.push_back(1);

   for(int x : v){
      while(ans.size() >= 2 and !is_clockwise(ans[ans.size()-2], ans.back(), x)) ans.pop_back();
      ans.push_back(x);
   }
   return ans;
}

inline void solve(){
   int n = get_n();

   vector<int> a{2}, b{2};
   for(int i=3; i<=n; i++){
      (is_clockwise(1, 2, i) ? b : a).push_back(i);
   }

   a = func(a);
   b = func(b);
   int ans = a.size() + b.size() - 2;

   a.push_back(1);
   while(min(a.size(), b.size()) >= 3 and is_clockwise(b[b.size()-2], a[1], b.back())) ans--, b.pop_back();
   while(min(a.size(), b.size()) >= 3 and is_clockwise(a[a.size()-2], b[2], a.back())) ans--, a.pop_back();

   give_answer(ans);
}

signed main(){
   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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