Submission #1034921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034921		Tob	Triangles (CEOI18_tri)	C++14	100 / 100	21 ms	2776 KiB

tri

#include <bits/stdc++.h>

#include "trilib.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef long double ld;
typedef pair <ld, ld> pdd;

const int N = 40007;
/*
static int n;
static long long *x, *y;
static int queries=0;

static void init() {
	static int is_inited=0;
	if (is_inited)
		return;
	is_inited=1;
	assert(scanf("%d", &n)==1);
	x=(long long*)malloc((n+1)*sizeof(long long));
	y=(long long*)malloc((n+1)*sizeof(long long));
	for (int i=1; i<=n; i++)
		assert(scanf("%lld%lld", &x[i], &y[i])==2);
}

int get_n() {
	init();
	return n;
}

int is_clockwise(int a, int b, int c) {
	init();
	assert(a>=1 && a<=n);
	assert(b>=1 && b<=n);
	assert(c>=1 && c<=n);
	assert(a!=b && a!=c && b!=c);
	queries++;
        if(queries == 1000 * 1000 + 1)
            printf("Too many queries!");
	return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0;
}

void give_answer(int s) {
	init();
	printf("%d\n", s);
}*/

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

bool cmp(int x, int y) {
	return is_clockwise(1, x+1, y+1);
}

void rek(vector <int>& v) {
	int m = ((int)v.size())/2;
	if (!m) return;
	vector <int> a, b;
	for (int i = 0; i < m; i++) a.pb(v[i]);
	for (int i = m; i < v.size(); i++) b.pb(v[i]);
	rek(a); rek(b);
	for (int i = 0, j = 0, k = 0; k < v.size(); k++) {
		if (i == a.size()) v[k] = b[j++];
		else if (j == b.size()) v[k] = a[i++];
		else {
			if (cmp(a[i], b[j])) v[k] = a[i++];
			else v[k] = b[j++];
		}
	}
}

int bio[N];

int main () {
	int n = get_n();
	
	vector <int> v[2];
	for (int i = 2; i < n; i++) v[cmp(1, i)].pb(i);
	rek(v[1]);
	rek(v[0]);
	vector <int> u;
	auto dod = [&](int x) {while (u.size() > 1 && ccw(u[u.size()-2]+1, u.back()+1, x+1)) u.pop_back(); u.pb(x);};
	for (int ii = 0; ii < 2; ii++) {
		dod(0); dod(1);
		for (int x : v[1]) dod(x);
		if (!v[0].empty()) dod(0);
		for (int x : v[0]) dod(x);
	}
	reverse(all(u));
	int cnt = 0;
	memset(bio, -1, sizeof bio);
	for (int i = 0; i < u.size(); i++) {
		if (bio[u[i]] != -1) {
			cnt -= bio[u[i]];
			break;
		}
		cnt++;
		bio[u[i]] = i;
	}
	give_answer(cnt);
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void rek(std::vector<int>&)':
tri.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = m; i < v.size(); i++) b.pb(v[i]);
      |                  ~~^~~~~~~~~~
tri.cpp:74:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 0, j = 0, k = 0; k < v.size(); k++) {
      |                                ~~^~~~~~~~~~
tri.cpp:75:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   if (i == a.size()) v[k] = b[j++];
      |       ~~^~~~~~~~~~~
tri.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   else if (j == b.size()) v[k] = a[i++];
      |            ~~^~~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

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