Submission #169878

#	Time	Username	Problem	Language	Result	Execution time	Memory
169878		arnold518	Triangles (CEOI18_tri)	C++14	100 / 100	34 ms	2596 KiB

tri

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
unordered_map<ll, bool> M;

ll f(int a, int b, int c)
{
	int aa, bb, cc;
	if(a<b && a<c) aa=a, bb=b, cc=c;
	if(b<a && b<c) aa=b, bb=c, cc=a;
	if(c<a && c<b) aa=c, bb=a, cc=b;
	return MAXN*(MAXN*aa+bb)+cc;
}

bool ccw(int a, int b, int c)
{
	//if(M.find(f(a, b, c))!=M.end()) return M[f(a, b, c)];
	//if(M.find(f(c, b, a))!=M.end()) return !M[f(c, b, a)];
	bool t=is_clockwise(a, b, c);
	//M[f(a, b, c)]=!t;
	//M[f(c, b, a)]=t;
	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);
	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:55:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
tri.cpp: In function 'void mergesortB(int, int)':
tri.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
tri.cpp: In function 'int main()':
tri.cpp:72:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
tri.cpp: In function 'll f(int, int, int)':
tri.cpp:39:26: warning: 'cc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return MAXN*(MAXN*aa+bb)+cc;
         ~~~~~~~~~~~~~~~~~^~~
tri.cpp:39:22: warning: 'bb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return MAXN*(MAXN*aa+bb)+cc;
              ~~~~~~~~^~~~
tri.cpp:39:19: warning: 'aa' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return MAXN*(MAXN*aa+bb)+cc;
               ~~~~^~~

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