Submission #145873

#	Time	Username	Problem	Language	Result	Execution time	Memory
145873		nvmdava	Triangles (CEOI18_tri)	C++17	55 / 100	1752 ms	916 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;
int res = 1;
int main() {

	n = get_n();

	int v1 = rng() % n + 1, v2 = rng () % n + 1;
	while(v1 == v2){
		v1 = rng() % n + 1;
		v2 = rng() % n + 1;
	}
	while(true){
		int i;
		for(i = 1; i <= n; i++){
			if(v1 == i || v2 == i) continue;
			if(is_clockwise(v1, v2, i) == 0){
				if(rng() % 2 == 0)
					v1 = i;
				else 
					v2 = i;
				break;
			}
		}
		if(i == n + 1) break;
	}

	int s = v1;

	while(v2 != s){
		res++;
		for(int i = 1; i <= n; i++){
			if(i == v1 || i == v2) continue;
			if(is_clockwise(v1, v2, i)){
				v1 = i;
			}
		}
		swap(v2, v1);
	}

	give_answer(res);
}

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