Submission #582633

#	Time	Username	Problem	Language	Result	Execution time	Memory
582633		amunduzbaev	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	304 KiB

tri

#include "trilib.h"
#ifndef EVAL
#include "trilib.c"
#endif
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

//~ void WA(){
	//~ give_answer(n + 1);
	//~ exit(0);
//~ }

vector<int> Sort(int l, int r){
	if(l == r) return {l};
	
	int m = (l + r) >> 1;
	auto lx = Sort(l, m), rx = Sort(m + 1, r);
	vector<int> res;
	l = 0, r = 0;
	while(l < (int)lx.size() || r < (int)rx.size()){
		if(l < (int)lx.size() && r < (int)rx.size()){
			if(is_clockwise(1, lx[l], rx[r])){
				res.push_back(lx[l++]);
			} else {
				res.push_back(rx[r++]);
			}
		} else if(l < (int)lx.size()){
			res.push_back(lx[l++]);
		} else {
			res.push_back(rx[r++]);
		}
	}
	
	return res;
}

signed main(){
	//~ ios::sync_with_stdio(0); cin.tie(0);
	
	int n = get_n();
	vector<int> p = Sort(2, n);
	int m = p.size(), sz = 0;
	vector<int> last, is(n, 1);
	is[0] = 0;
	for(int i=0;i<m;i++){
		while(sz > 1 && !is_clockwise(last[sz - 2], last[sz - 1], p[i])){
			is[last.back() - 1] = 0;
			last.pop_back();
			sz--;
		}
		last.push_back(p[i]);
		sz++;
	}
	
	auto check = [&](int a, int b){
		ar<int, 2> cc {};
		for(int i=1;i<=n;i++){
			if(i == a || i == b) continue;
			cc[is_clockwise(a, b, i)]++;
		}
		
		return (cc[0] == 0 || cc[1] == 0);
	};
	
	if(check(1, last[0]) && check(1, last[sz - 1])){
		give_answer((int)last.size() + 1);
		return 0;
	}
	
	for(int i=0;i<m;i++){
		while(sz > 1 && !is_clockwise(last[sz - 2], last[sz - 1], p[i])){
			is[last.back() - 1] = 0;
			last.pop_back();
			sz--;
		}
		
		last.push_back(p[i]);
		sz++;
	}
	
	int sum = accumulate(is.begin(), is.end(), 0);
	give_answer(sum);
	return 0;
}

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