Submission #1229466

#TimeUsernameProblemLanguageResultExecution timeMemory
1229466radodododoTriangles (CEOI18_tri)C++20
75 / 100
23 ms1604 KiB
#include <iostream> #include <vector> #include <algorithm> #include <random> 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 mt19937 ggg; long long ccin_n() { return get_n(); /*long long zzz; cin >> zzz; return zzz;*/ } vector<long long> reall; bool aski(long long a, long long b, long long c) { return is_clockwise(reall[a] + 1, reall[b] + 1, reall[c] + 1); /*cout << "? " << a << " " << b << " " << c << '\n'; bool okak; cin >> okak; return okak;*/ } 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); //cout << "! " << x; } int main() { long long n = ccin_n(); vector<long long> srt(n); for (long long i = 0; i < n; i++) { srt[i] = i; } reall = srt; shuffle(reall.begin(), reall.end(), ggg); sort(srt.begin(), srt.end(), cmpp); long long ii = -1; for (long long i = 1; i + 1 < n; i++) { if (aski(0, srt[i], srt[i + 1])) { ii = i + 1; break; } } 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]); } //cout << ii << " " << srt[ii] << '\n'; srt = newsrt; /*for (auto gh : srt) { cout << gh << " "; } cout << '\n';*/ 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); } /*for (auto gh : ch) { cout << gh << " "; } cout << '\n';*/ 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...