이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <vector>
#include "trilib.h"
using namespace std;
vector<int> componenta[ 2 ];
vector<int> divide[ 2 ];
int n;
inline bool cmp( const int& a, const int& b ) {
return ( a == b ? false : is_clockwise( 1, a, b ) );
}
int main()
{
n = get_n();
for( int i = 0; i < 2; i++ )
divide[ i ].push_back( 2 );
for( int i = 3; i <= n; i++ )
divide[ is_clockwise( 1, 2, i ) ].push_back( i );
for( int comp = 0; comp < 2; comp++ ) {
sort( divide[ comp ].begin(), divide[ comp ].end(), cmp );
for( vector<int>::iterator it = divide[ comp ].begin(); it != divide[ comp ].end(); it++ ) {
int right = componenta[ comp ].size();
while( right > 1 && !is_clockwise( componenta[ comp ][ right - 2 ], componenta[ comp ].back(), *it ) ) {
componenta[ comp ].pop_back();
right--;
}
componenta[ comp ].push_back( *it );
}
if( comp )
reverse( componenta[ comp ].begin(), componenta[ comp ].end() );
componenta[ comp ].insert( componenta[ comp ].begin(), 1 );
}
/*for( int comp = 0; comp < 2; comp++ ) {
for( int i : componenta[ comp ] )
cout << i << ' ';
cout << '\n';
}*/
if( min( componenta[ 0 ].size(), componenta[ 1 ].size() ) == 1 ) {
give_answer( max( componenta[ 0 ].size(), componenta[ 1 ].size() ) );
exit( 0 );
}
for( int comp = 0; comp < 2; comp++ ) {
componenta[ 0 ].pop_back();
bool good = false;
while( !good ) {
good = true;
if( componenta[ 0 ].size() > 1 && !( comp ^ is_clockwise( componenta[ 0 ][ componenta[ 0 ].size() - 2 ], componenta[ 0 ].back(), componenta[ 1 ].back() ) ) ) {
componenta[ 0 ].pop_back();
good = false;
}
if( componenta[ 1 ].size() > 1 && !( comp ^ is_clockwise( componenta[ 0 ].back(), componenta[ 1 ].back(), componenta[ 1 ][ componenta[ 1 ].size() - 2 ] ) ) ) {
componenta[ 1 ].pop_back();
good = false;
}
}
swap( componenta[ 0 ], componenta[ 1 ] );
}
give_answer( componenta[ 0 ].size() + componenta[ 1 ].size() );
return 0;
}
/*
6
1 1
4 3
2 2
1 4
5 1
3 2
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |