제출 #73331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73331		zscoder	Triangles (CEOI18_tri)	C++17	20 / 100	4 ms	780 KiB

tri

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "trilib.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int nn; int god;
map<int,bool> ma;

int hsh(int x, int y, int z)
{
	return (x<<18)^(y<<9)^z;
}

bool ex(int x, int y, int z)
{
	return (ma.find(hsh(x,y,z))!=ma.end());
}

bool is_cl(int x, int y, int z)
{
	/*
	if(ex(x,y,z)) return ma[hsh(x,y,z)];
	if(ex(x,z,y)) return !ma[hsh(x,z,y)];
	if(ex(y,x,z)) return !ma[hsh(y,x,z)];
	if(ex(y,z,x)) return ma[hsh(y,z,x)];
	if(ex(z,x,y)) return ma[hsh(z,x,y)];
	if(ex(z,y,x)) return !ma[hsh(z,y,x)];
	return (ma[hsh(x,y,z)] = is_clockwise(x+1,y+1,z+1));
	*/
	return is_clockwise(x+1,y+1,z+1);
}
bool cmp(int x, int y)
{
	return is_cl(god,x,y);
}
int ans;

int get_lowest(vi v)
{
	if(v.size()==1) return v[0];
	random_shuffle(v.begin(),v.end());
	int u = v[0];
	vector<int> vec;
	for(int i=0;i<nn;i++)
	{
		if(u!=i) vec.pb(i);
	}
	god=u;
	stable_sort(vec.begin(),vec.end(),cmp);
	int id=int(vec.size());
	for(int i=int(vec.size())-1;i>=0;i--)
	{
		if(is_cl(god,vec[i],vec[0]))
		{
			id=i; 
		}
		else break;
	}
	if(id==int(vec.size())) return u;
	int mid=int(v.size())/2;
	if(id>=mid)
	{
		vi nw;
		for(int i=id;i<v.size();i++)
		{
			nw.pb(v[i]);
		}
		return get_lowest(nw);
	}
	else
	{
		vi nw;
		for(int i=0;i<id;i++)
		{
			nw.pb(v[i]);
		}
		return get_lowest(nw);
	}
}

void solve_init(int u)
{
	vector<int> vec;
	for(int i=0;i<nn;i++)
	{
		if(u!=i) vec.pb(i);
	}
	god=u;
	stable_sort(vec.begin(),vec.end(),cmp);
	if(is_cl(god,vec.back(),vec.front())) return ;
	vector<int> S;
	S.pb(u);
	S.pb(vec[0]); S.pb(vec[1]);
	for(int i=2;i<vec.size();i++)
	{
		int u=vec[i];
		while(S.size()>=2&&!is_cl(S[int(S.size())-2], S[int(S.size())-1], u))
		{
			S.pop_back();
		}
		S.pb(u);
	}
	ans=min(ans,int(S.size()));
}

int main()
{
	nn = get_n();
	ans = nn;
	vector<int> vertices;
	for(int i=0;i<nn;i++) vertices.pb(i);
	if(nn>15000)
	{
		for(int i=0;i<nn;i++)
		{
			if(nn>500&&i>=2) break;
			solve_init(vertices[i]);
		}
	}
	else
	{
		int v = get_lowest(vertices);
		solve_init(v);
	}
	give_answer(ans);
}

컴파일 시 표준 에러 (stderr) 메시지

tri.cpp: In function 'int get_lowest(vi)':
tri.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=id;i<v.size();i++)
                ~^~~~~~~~~
tri.cpp: In function 'void solve_init(int)':
tri.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2;i<vec.size();i++)
              ~^~~~~~~~~~~

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