Submission #917965

#	Time	Username	Problem	Language	Result	Execution time	Memory
917965		PM1	Triangles (CEOI18_tri)	C++17	0 / 100	3063 ms	516 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
const int mxn=500+5;
int n,mark[mxn],ans=3,nxt[mxn],pre[mxn],st=1;
void merge(int x,int y){
	pre[y]=x;
	nxt[x]=y;
}
int main(){
	n=get_n();
	if(is_clockwise(1,2,3)){
		merge(1,2);
		merge(2,3);
		merge(3,1);
	}
	else{
		merge(2,1);
		merge(3 ,2);
		merge(1,3);
	}
	for(int i=4;i<=n;i++){
		while(!mark[st]){
			mark[st]=1;
			if(is_clockwise(st,nxt[st],i)){
				st=nxt[st];
				continue;
			}
			ans++;
			merge(i,nxt[st]);
			merge(st,i);
			while(!is_clockwise(i,nxt[i],nxt[nxt[i]])){
				ans--;
				merge(i,nxt[nxt[i]]);
			}
			while(!is_clockwise(pre[st],st,i)){
				ans--;
				merge(pre[st],i);
			}
		}
		memset(mark,0,sizeof mark);
	}
	give_answer(ans);
	return 0;
}

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