Submission #169881

#	Time	Username	Problem	Language	Result	Execution time	Memory
169881		arnold518	Triangles (CEOI18_tri)	C++14	100 / 100	30 ms	2552 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MAXN = 40001;

int N, p, q;
vector<int> A, B;
list<int> C;

list<int>::iterator bef(list<int>::iterator t)
{
	if(t!=C.begin()) return prev(t);
	else return prev(C.end());
}

list<int>::iterator nxt(list<int>::iterator t)
{
	if(t==prev(C.end())) return C.begin();
	else return next(t);
}

int cnt=0;

bool ccw(int a, int b, int c)
{
	bool t=is_clockwise(a, b, c);
	return !t;
}

void mergesortA(int l, int r)
{
	if(l+1==r) return;
	int mid=l+r>>1;
	mergesortA(l, mid);
	mergesortA(mid, r);
	inplace_merge(A.begin()+l, A.begin()+mid, A.begin()+r, [&](const int &p, const int &q) { return ccw(1, p, q); });
}

void mergesortB(int l, int r)
{
	if(l+1==r) return;
	int mid=l+r>>1;
	mergesortB(l, mid);
	mergesortB(mid, r);
	inplace_merge(B.begin()+l, B.begin()+mid, B.begin()+r, [&](const int &p, const int &q) { return !ccw(1, p, q); });
}

int main()
{
	int i, j;
	N=get_n();

	for(i=3; i<=N; i++)
	{
		if(ccw(1, 2, i)) A.push_back(i);
		else B.push_back(i);
	}

	A.push_back(2); B.push_back(2);
	stable_sort(A.begin(), A.end(), [&](const int &p, const int &q) { return ccw(1, p, q); });
	stable_sort(B.begin(), B.end(), [&](const int &p, const int &q) { return !ccw(1, p, q); });
	//mergesortA(0, A.size());
	//mergesortB(0, B.size());

	A.insert(A.begin(), 1);
	B.insert(B.begin(), 1);

	vector<int> S;
	for(auto it : A)
	{
		while(S.size()>1 && !ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	A=S; S.clear();

	for(auto it : B)
	{
		while(S.size()>1 && ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	B=S; S.clear();	

	A.erase(A.begin()); A.erase(A.begin());
	B.erase(B.begin()); B.erase(B.begin()); 
	reverse(B.begin(), B.end());

	queue<list<int>::iterator> Q;
	C.push_back(1);
	for(auto it : B) C.push_back(it);
	C.push_back(2);
	for(auto it : A) C.push_back(it);

	set<int> vis;
	for(auto it=C.begin(); it!=C.end(); it++) if(!ccw(*bef(it), *it, *nxt(it))) Q.push(it), vis.insert(*it);

	while(!Q.empty() && C.size()>3)
	{
		auto now=Q.front(); Q.pop();
		
		auto l=bef(now), r=nxt(now);
		C.erase(now);

		if(vis.find(*l)==vis.end() && !ccw(*bef(l), *l, *nxt(l))) Q.push(l), vis.insert(*l);
		if(vis.find(*r)==vis.end() && !ccw(*bef(r), *r, *nxt(r))) Q.push(r), vis.insert(*r);
	}
	give_answer(C.size());
}

Compilation message (stderr)

tri.cpp: In function 'void mergesortA(int, int)':
tri.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
tri.cpp: In function 'void mergesortB(int, int)':
tri.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
tri.cpp: In function 'int main()':
tri.cpp:55:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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