| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1229461 | radodododo | Triangles (CEOI18_tri) | C++20 | 0 ms | 0 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_64 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;
random_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());
}
}