Submission #246306

#	Time	Username	Problem	Language	Result	Execution time	Memory
246306		eohomegrownapps	Triangles (CEOI18_tri)	C++14	100 / 100	338 ms	47756 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
int get_n();
int is_clockwise(int a, int b, int c);
void give_answer(int s);
*/
 
int n;
 
int cns = 40000;
unordered_map<int,bool> cwmap[40000];
int numhashed = 0;
 
bool cwhash(int a, int b, int c){
	int ct = b*cns+c;
	auto f = cwmap[a].find(ct);
	if (f!=cwmap[a].end()){
		return cwmap[a][ct];
	} else {
		if (numhashed<=1000000){
			numhashed++;
			return cwmap[a][ct]=bool(is_clockwise(a+1,b+1,c+1));
		} else {
			return bool(is_clockwise(a+1,b+1,c+1));
		}
	}
}
 
bool cw(int a, int b, int c){
	//cout<<"cw "<<a<<" "<<b<<" "<<c<<" ";
	int minv = min(min(a,b),c);
	int tmp;
	if (a!=minv){
		tmp=a;a=b;b=c;c=tmp;
	}
	if (a!=minv){
		tmp=a;a=b;b=c;c=tmp;
	}
	if (b<c){
		return cwhash(a,b,c);
	} else {
		return !cwhash(a,c,b);
	}
	//cout<<ans<<'\n';
}
/*int pcnt = 0;
bool cw(int a, int b, int c){
	pcnt++;
	assert(pcnt<=1000000);
	return is_clockwise(a+1,b+1,c+1);
}*/
 
vector<int> pts;
vector<int> rhs;
vector<int> lhs;
vector<int> hull;
int convexhull(int s, int e){
	/*cout<<s<<" "<<e<<'\n';
	cout<<"find hull ";
	for (int i = s; i<e; i++){
		cout<<pts[i]<<" ";
	}cout<<'\n';*/
	if (e-s<=3){
		if (e-s==3&&!cw(pts[s],pts[s+1],pts[s+2])){
			swap(pts[s+1],pts[s+2]);
		}
		return e-s;
	}
	int a = pts[s];
	int b = pts[s+1];
	//a to b
	lhs.clear();
	rhs.clear();
	for (int i = s+2; i<e; i++){
		if (cw(a,b,pts[i])){
			lhs.push_back(pts[i]);
		} else {
			rhs.push_back(pts[i]);
		}
	}
	if (lhs.size()>rhs.size()){
		swap(lhs,rhs);
		swap(a,b);
	}
	lhs.push_back(a);
	lhs.push_back(b);
	assert(s+lhs.size()+rhs.size()==e);
	for (int i = s; i<s+lhs.size(); i++){
		pts[i]=lhs[i-s];
	}
	for (int i = s+lhs.size(); i<e; i++){
		pts[i]=rhs[i-s-lhs.size()];
	}
	/*cout<<"lhs: ";
	for (int i : lhs){
		cout<<i<<" ";
	}cout<<'\n';
	cout<<"rhs: ";
	for (int i : rhs){
		cout<<i<<" ";
	}cout<<'\n';
	for (int i : pts){
		cout<<i<<" ";
	}cout<<'\n';*/
	int rf = rhs.size();
	int lf = lhs.size();
	int ls = convexhull(s,s+lf);
	int rs = convexhull(s+lf,e);
	/*cout<<"merge:\n";
	for (int i = s; i<s+ls; i++){
		cout<<pts[i]<<" ";
	}cout<<'\n';
	for (int j = s+lf;j<s+lf+rs; j++){
		cout<<pts[j]<<" ";
	}cout<<'\n';*/
	//now in sorted order
	int leftpt = b;
	
	int rightpt = pts[s+lf];
	int leftind = -1;
	int rightind = 0;
	for (int i = 0; i<rs; i++){
		if (rf>1&&cw(pts[s+lf+(i+1)%rs],pts[s+lf+i],leftpt)){
			rightpt=pts[s+lf+i];
			rightind = i;
			break;
		}
	}
	assert(rightpt!=-1);
	leftind = find(pts.begin()+s,pts.begin()+s+lf,leftpt)-(pts.begin()+s);
	//cout<<leftpt<<" "<<rightpt<<'\n';
	//cout<<leftind<<" "<<rightind<<'\n';
	int lp2 = leftind;
	int rp1 = rightind;
	bool check;
	bool condexit;
	do {
		check = true;
		condexit = true;
		while (ls>1&&!cw(pts[s+lf+rp1],pts[s+lp2],pts[s+(lp2+1)%ls])){
			if (ls>1&&rs>1&&!cw(pts[s+(lp2+1)%ls],pts[s+lf+rp1],pts[s+lf+(rp1+rs-1)%rs])&&cw(pts[s+lf+rp1],pts[s+lf+(rp1+rs-1)%rs],pts[s+lp2])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"inc lp2\n";
			lp2+=1;
			lp2%=ls;
			check = false;
		}
		while (rs>1&&cw(pts[s+lp2],pts[s+lf+rp1],pts[s+lf+(rp1+rs-1)%rs])){
			if (ls>1&&rs>1&&cw(pts[s+lf+(rp1+rs-1)%rs],pts[s+lp2],pts[s+(lp2+1)%ls])&&!cw(pts[s+lp2],pts[s+(lp2+1)%ls],pts[s+lf+rp1])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"dec rp1\n";
			rp1+=rs-1;
			rp1%=rs;
			check = false;
		}
	} while (!check);
	assert(condexit==true);
	int lp1 = leftind;
	int rp2 = rightind;
	do {
		check = true;
		condexit = true;
		while (ls>1&&cw(pts[s+lf+rp2],pts[s+lp1],pts[s+(lp1+ls-1)%ls])){
			//cout<<"vis\n";
			//cout<<pts[s+lp1]<<" "<<pts[s+ls+rp2]<<'\n';
			if (ls>1&&rs>1&&cw(pts[s+(lp1+ls-1)%ls],pts[s+lf+rp2],pts[s+lf+(rp2+1)%rs])&&!cw(pts[s+lf+rp2],pts[s+lf+(rp2+1)%rs],pts[s+lp1])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"dec lp1\n";
			lp1+=ls-1;
			lp1%=ls;
			check = false;
		}
		while (rs>1&&!cw(pts[s+lp1],pts[s+lf+rp2],pts[s+lf+(rp2+1)%rs])){
			if (ls>1&&rs>1&&!cw(pts[s+lf+(rp2+1)%rs],pts[s+lp1],pts[s+(lp1+ls-1)%ls])&&cw(pts[s+lp1],pts[s+(lp1+ls-1)%ls],pts[s+lf+rp2])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"inc rp2\n";
			rp2+=1;
			rp2%=rs;
			check = false;
		}
	} while (!check);
	assert(condexit==true);
	//cout<<pts[s+lp1]<<" "<<pts[s+lp2]<<'\n';
	//cout<<pts[s+ls+rp1]<<" "<<pts[s+ls+rp2]<<'\n';
	hull.clear();
	int ptr;
	ptr = rp2;
	while (ptr!=rp1) {
		hull.push_back(pts[s+lf+ptr]);
		ptr++;
		ptr%=rs;
	}
	hull.push_back(pts[s+lf+ptr]);
	ptr = lp2;
	while (ptr!=lp1) {
		hull.push_back(pts[s+ptr]);
		ptr++;
		ptr%=ls;
	}
	hull.push_back(pts[s+ptr]);
	for (int i = s; i<s+hull.size(); i++){
		pts[i]=hull[i-s];
	}
	
	/*cout<<"hull contains ";
	for (int i : hull){
		cout<<i<<' ';
	}cout<<'\n';*/
	int hs = hull.size();
	return hs;
}
 
int main(){
	n = get_n();
	pts.resize(n);
	iota(pts.begin(),pts.end(),0);
    std::mt19937 g(1234588);
	shuffle(pts.begin(),pts.end(),g);
	give_answer(convexhull(0,n));
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from tri.cpp:2:
tri.cpp: In function 'int convexhull(int, int)':
tri.cpp:90:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(s+lhs.size()+rhs.size()==e);
         ~~~~~~~~~~~~~~~~~~~~~~~^~~
tri.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = s; i<s+lhs.size(); i++){
                  ~^~~~~~~~~~~~~
tri.cpp:216:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = s; i<s+hull.size(); i++){
                  ~^~~~~~~~~~~~~~

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