Submission #121189

#	Time	Username	Problem	Language	Result	Execution time	Memory
121189		bekzhan29	Triangles (CEOI18_tri)	C++14	100 / 100	43 ms	2556 KiB

tri

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include "trilib.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 3e9
#define mod 998244353
#define eps 1e-6
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
void read(ll &x)
{
	scanf("%lld",&x);
}
void read(ll &x, ll &y)
{
	scanf("%lld%lld",&x,&y);
}
void read(ll &x, ll &y, ll &z)
{
	scanf("%lld%lld%lld",&x,&y,&z);
}
void print(ll x)
{
	printf("%lld ",x);
}
void println(ll x)
{
	printf("%lld\n",x);
}
const ll N=300100;
ll n,a[N],b[N],sz,mid,cnt,res,mx=1000000,l,r;
bool cmp(ll x, ll y)
{
	return b[x]<b[y];
}
bool cmp1(ll x, ll y)
{
	cnt++;
	assert(cnt<=mx);
	return is_clockwise(1,x,y);
}
int main()
{
	n=get_n();
	for(ll i=1;i<=n;i++)
		a[i]=i;
	for(ll i=3;i<=n;i++)
	{
		cnt++;
		assert(cnt<=mx);
		if(is_clockwise(1,2,i))
			b[i]=1;
		else
			b[i]=-1;
	}
	b[2]=0;
	sort(a+2,a+n+1,&cmp);
	for(ll i=3;i<=n;i++)
	{
		if(b[a[i]]<b[a[i-1]])
		{
			for(ll i=1;i>=0;i++);
		}
	}
	for(ll i=2;i<=n;i++)
		if(b[a[i]]==0)
			mid=i;
	sort(a+2,a+mid,&cmp1);
	sort(a+mid+1,a+n+1,&cmp1);
	sz=2;
	b[1]=1;
	b[2]=a[2];
	for(ll i=3;i<=n;i++)
	{
		while(sz>=2&&!is_clockwise(b[sz-1],b[sz],a[i]))
			sz--;
		b[++sz]=a[i];
	}
	l=1;
	r=sz;
	for(ll ch=1;ch&&r-l+1>=3;)
	{
		ch=0;
		if(!is_clockwise(b[r],b[l],b[l+1]))
			l++,ch=1;
		else if(is_clockwise(b[l],b[r],b[r-1]))
			r--,ch=1;
	}
	give_answer(r-l+1);
}

Compilation message (stderr)

tri.cpp: In function 'void read(ll&)':
tri.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&x);
  ~~~~~^~~~~~~~~~~
tri.cpp: In function 'void read(ll&, ll&)':
tri.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&x,&y);
  ~~~~~^~~~~~~~~~~~~~~~~~
tri.cpp: In function 'void read(ll&, ll&, ll&)':
tri.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&x,&y,&z);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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