Submission #145901

#	Time	Username	Problem	Language	Result	Execution time	Memory
145901		nvmdava	Triangles (CEOI18_tri)	C++17	75 / 100	400 ms	66676 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;

map<ll, bool> lol;

bool get(ll a, ll b, ll c){
	ll en = a * 40001 * 40001 + b * 40001 + c;
	if(lol.find(en) != lol.end())
		return lol[en];
	return lol[en] = is_clockwise(a, b, c);
}

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);
 	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:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < hull.size(); i++){
                   ~~^~~~~~~~~~~~~
tri.cpp:61: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