Submission #1214274

#TimeUsernameProblemLanguageResultExecution timeMemory
1214274ByeWorldTriangles (CEOI18_tri)C++20
75 / 100
2065 ms271748 KiB
#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>, int> 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 >= 720'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++){ 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){ 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++){ if(clock(1, 2, i)) dw.pb(i); else up.pb(i); } sort(dw.begin(), dw.end(), cmp); sort(up.begin(), up.end(), cmp); // 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 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...