#include "trilib.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<int,pii> ipii;
typedef pair<pii,int> piii;
const int MAXN = 1e7+10;
const int SQRT = 450;
const int INF = 1e9+10;
const int MOD = 998244353;
const int LOG = 30;
int n;
vector<int> up, dw, urut;
int que;
map<array<int,3>, bool> ma;
bool clock(int x, int y, int z){
// if(ma.find({x,y,z}) != ma.end()) return ma[{x,y,z}];
que++;
if(que >= 760'000) assert(false);
bool ret = is_clockwise(x,y,z);
// ma[{x,y,z}] = ma[{y,z,x}] = ma[{z,x,y}] = ret;
// ma[{x,z,y}] = ma[{z,y,x}] = ma[{y,x,z}] = 1-ret;
return ret;
}
bool cmp(int a, int b){
if(clock(2, a, b)) return 1;
return 0;
}
vector<int> ANS;
void solve(){
ANS.clear();
ANS.pb(urut[0]); ANS.pb(urut[1]);
for(int i=2; i<urut.size(); i++){ // N
while(ANS.size()>=2 && !clock(
ANS[ANS.size()-2], ANS.back(), urut[i]) ) ANS.pop_back();
ANS.pb(urut[i]);
}
bool done = 0;
while(!done){ // N - 2N
done = 1;
while(ANS.size() > 3 &&
!clock( ANS.back(), ANS[0], ANS[1]) ){
vector<int> vec;
for(int j=1; j<ANS.size(); j++){
vec.pb(ANS[j]);
}
ANS = vec;
done = 0; break;
}
if(!done) continue;
while(ANS.size() > 3 &&
!clock(ANS[ANS.size()-2], ANS.back(), ANS[0]) ){
vector<int> vec;
for(int j=0; j+1<ANS.size(); j++){
vec.pb(ANS[j]);
}
ANS = vec;
done = 0; break;
}
}
}
signed main(){
n = get_n();
if(n==3){ give_answer(n); exit(0); }
for(int i=3; i<=n; i++){ // N
if(clock(1, 2, i)) dw.pb(i);
else up.pb(i);
}
sort(dw.begin(), dw.end(), cmp); // X log X
sort(up.begin(), up.end(), cmp); // N-X log N-X
// N log N
// for(auto in : up) cout << in << " up\n";
// for(auto in : dw) cout << in << " dw\n";
urut.pb(1);
for(auto in : up) urut.pb(in);
urut.pb(2);
for(auto in : dw) urut.pb(in);
solve();
give_answer((int)ANS.size());
}
# | 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... |