Submission #917968

#	Time	Username	Problem	Language	Result	Execution time	Memory
917968		PM1	Triangles (CEOI18_tri)	C++17	55 / 100	3 ms	1368 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);
				st=pre[st];
			}
			break;
		}
		memset(mark,0,sizeof mark);
	}
	give_answer(ans);
	return 0;
}

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