Submission #145917

#	Time	Username	Problem	Language	Result	Execution time	Memory
145917		nvmdava	Triangles (CEOI18_tri)	C++17	75 / 100	3054 ms	207968 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
 
#define ff first
#define ss second
#define ll long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, root, t;

unordered_map<ll, bool> lol;

ll enc(ll a, ll b, ll c){
	return a * 40001 * 40001 + b * 40001 + c;
}

bool get(ll a, ll b, ll c){
	ll en = enc(a, b, c);
	if(lol.find(en) != lol.end())
		return lol[en];
	int res = is_clockwise(a, b, c);
	lol[enc(a, b, c)] = lol[enc(b, c, a)] = lol[enc(c, a, b)] = res;
	lol[enc(c, b, a)] = lol[enc(b, a, c)] = lol[enc(a, c, b)] = res ^ 1;
	return res;
}

class Compare{
	public:
		bool operator()(const int& lhs, const int& rhs){
			return get(root, lhs, rhs);
		}
};


set<int, Compare> le, ri;
vector<int> hull, hull2;
int main() {
 
	n = get_n();
 
 	root = rng() % n + 1;
 	t = rng() % n + 1;
 	while(root == t){
 		root = rng() % n + 1;
 		t = rng() % n + 1;
 	}
 	
 	for(int i = 1; i <= n; i++){
 		if(root == i || t == i) continue;
 		if(get(t, root, i))
 		 	ri.insert(i);
 		else 
 			le.insert(i);
 	}
 	
 	for(int x : le)
 		hull.push_back(x);
 	hull.push_back(root);
 	for(int x : ri)
 		hull.push_back(x);
 	hull.push_back(t);

 	int v1 = hull[0];
 	int v2 = hull[1];
 	hull2.push_back(v1);
 	hull2.push_back(v2);
 	for(int i = 2; i < hull.size(); i++){
 		while(hull2.size() > 2 && get(hull2[hull2.size() - 2], hull2[hull2.size() - 1], hull[i]) == 0) hull2.pop_back();
 		hull2.push_back(hull[i]);
 	}

 	swap(hull2, hull);
 	hull2.clear();

 	while(true){
 		for(int i = 0; i < hull.size(); i++){
 			int l = i - 1;
 			int r = i + 1;
 			if(l == -1) l = hull.size() - 1;
 			if(r == hull.size()) r = 0;
 			l = hull[l];
 			r = hull[r];
 			if(!hull2.empty())
 				l = hull2.back();

 			if(get(l, hull[i], r))
 				hull2.push_back(hull[i]);
 		}
 		swap(hull2, hull);
 		if(hull.size() == hull2.size()) break;
 		hull2.clear();
 	}
 	give_answer(hull.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 2; i < hull.size(); i++){
                  ~~^~~~~~~~~~~~~
tri.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < hull.size(); i++){
                   ~~^~~~~~~~~~~~~
tri.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r == hull.size()) r = 0;
        ~~^~~~~~~~~~~~~~

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