Submission #1229406

#TimeUsernameProblemLanguageResultExecution timeMemory
1229406radodododoTriangles (CEOI18_tri)C++20
0 / 100
1 ms580 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #ifdef __cplusplus extern "C" { #endif int get_n(); int is_clockwise(int a, int b, int c); void give_answer(int s); #ifdef __cplusplus } #endif long long ccin_n() { return get_n(); } bool aski(long long a, long long b, long long c) { return is_clockwise(a + 1, b + 1, c + 1); } bool cmpp(long long a, long long b) { if (a == 0) { return true; } if (a == 1) { return a < b; } if (b == 0) { return false; } if (b == 1) { return a < b; } bool aska = aski(1, 0, a); bool askb = aski(1, 0, b); if (aska && !askb) { return true; } if (!aska && askb) { return false; } return aski(a, 0, b); } void say_anse(long long x) { give_answer(x); } int main() { long long n = ccin_n(); vector<long long> srt(n); for (long long i = 0; i < n; i++) { srt[i] = i; } sort(srt.begin(), srt.end(), cmpp); long long ii = -1; for (long long i = 1; i + 1 < n; i++) { if (aski(0, i, i + 1)) { ii = i + 1; } } if (ii == -1) { vector<long long> ch; for (auto i : srt) { if (ch.size() < 2) { ch.push_back(i); continue; } while (ch.size() >= 2 && aski(ch[ch.size() - 2], ch.back(), i)) { ch.pop_back(); } ch.push_back(i); } vector<long long> sv = ch; vector<bool> delet(n); for (auto i : srt) { if (ch.size() < 2) { ch.push_back(i); continue; } while (ch.size() >= 2 && aski(ch[ch.size() - 2], ch.back(), i)) { delet[ch.back()] = 1; ch.pop_back(); } ch.push_back(i); } long long ans = sv.size(); for (auto x : sv) { if (delet[x]) { ans--; } } say_anse(ans); } else { vector<long long> newsrt = { 0 }; for (long long j = ii; j < n; j++) { newsrt.push_back(srt[j]); } for (long long j = 1; j < ii; j++) { newsrt.push_back(srt[j]); } srt = newsrt; vector<long long> ch; for (auto i : srt) { if (ch.size() < 2) { ch.push_back(i); continue; } while (ch.size() >= 2 && aski(ch[ch.size() - 2], ch.back(), i)) { ch.pop_back(); } ch.push_back(i); } say_anse(ch.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...