제출 #822978

#제출 시각아이디문제언어결과실행 시간메모리
822978MohamedAhmed04Triangles (CEOI18_tri)C++14
35 / 100
3089 ms239392 KiB
#include "trilib.h"
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 500 + 10 ;

int N ;

int cntq = 0 ;
map<int , bool>mp[MAX][MAX] ;

int Hash(int x , int y , int z)
{
	return (1ll * x * (N+1) * (N+1) + y * (N+1) + z) ;
}

int query(int x , int y , int z)
{
	if(mp[x][y].find(z) != mp[x][y].end())
		return mp[x][y][z] ;
	++cntq ;
	// if(cntq > 1e6)
	// 	while(1) ;
	int ans = is_clockwise(x , y , z) ;
	mp[x][y][z] = mp[y][z][x] = mp[z][x][y] = ans ;
	mp[x][z][y] = mp[y][x][z] = mp[z][y][x] = !ans ;
	return ans ;
}

int main()
{
	srand(time(NULL)) ;
	mt19937 rng(rand()) ;
	N = get_n() ;
	int ans = 0 ;
	vector<int>v ;
	for(int i = 1 ; i <= N ; ++i)
	{
		bool flag = false ;
		for(int j = 1 ; j <= N && (!flag) ; ++j)
		{
			v.clear() ;
			for(int k = 1 ; k <= N ; ++k)
			{
				if(i == j || i == k || j == k)
					continue ;
				v.push_back(k) ;
			}
			shuffle(v.begin() , v.end() , rng) ;
			flag = (i != j) ;
			for(auto &k : v)
			{
				if(!flag)
					break ;
				flag &= query(i , j , k) ;
			}
		}
		ans += flag ;
	}
	give_answer(ans) ;
	return 0 ;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...