Submission #1034916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034916		Tob	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	348 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;

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();
	
//	for (int i = 1; i <= n; i++) cin >> co[i].F >> co[i].S;
	
	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 && !is_clockwise(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);
		if (!v[1].empty()) dod(1);
		for (int x : v[1]) dod(x);
		if (!v[1].empty() && !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:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = m; i < v.size(); i++) b.pb(v[i]);
      |                  ~~^~~~~~~~~~
tri.cpp:31:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0, j = 0, k = 0; k < v.size(); k++) {
      |                                ~~^~~~~~~~~~
tri.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if (i == a.size()) v[k] = b[j++];
      |       ~~^~~~~~~~~~~
tri.cpp:33:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   else if (j == b.size()) v[k] = a[i++];
      |            ~~^~~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

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