이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;
void debug(string names) {
cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
int pos = 0;
for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
cout << names[pos];
cout << ": " << par << " ";
while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
pos++;
}
names.erase(names.begin(), names.begin() + pos);
debug(names, left...);
}
struct fenwick {
int n;
vector<int> tree;
fenwick() {}
fenwick(int sz) {
n = sz + 1;
tree.resize(n, 0);
}
void upd(int pos) {
for (pos++; pos <= n; pos += (pos & -pos)) tree[pos]++;
}
int query(int pos) {
int rtn = 0;
for (pos++; pos; pos -= (pos & -pos)) rtn += tree[pos];
return rtn;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
//#include "trilib.h"
int get_n() {
cout << "n? ";
int n;
cin >> n;
return n;
}
bool is_clockwise(int a, int b, int c) {
cout << "clock " << a << " " << b << " " << c << " ";
bool rtn;
cin >> rtn;
return rtn;
}
void give_answer(int s) {
cout << "answer: " << s << '\n';
}
bool clock(int a, int b, int c) {
return is_clockwise(1 + a, 1 + b, 1 + c);
}
int n;
bool cmp(int a, int b) {
return clock(0, a, b);
}
void merge(vector<int> &a, int l, int r) {
static int A[40404];
int mid = (l + r) / 2, nl = l, nr = mid + 1, nxt = l;
while (nl <= mid && nr <= r) {
if (cmp(a[nl], a[nr]))
A[nxt++] = a[nl++];
else
A[nxt++] = a[nr++];
}
while (nl <= mid) A[nxt++] = a[nl++];
while (nr <= r) A[nxt++] = a[nr++];
for (int i = l; i <= r; i++) a[i] = A[i];
}
void msort(vector<int> &a, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
msort(a, l, mid);
msort(a, mid + 1, r);
merge(a, l, r);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
n = get_n();
vector<int> L, R;
L.push_back(1);
for (int i = 2; i < n; i++)
if (clock(0, 1, i))
R.push_back(i);
else
L.push_back(i);
msort(L, 0, (int)L.size() - 1);
msort(R, 0, (int)R.size() - 1);
vector<int> c = { 0 };
for (auto &i : L) {
while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
c.push_back(i);
}
for (auto &i : R) {
while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
c.push_back(i);
}
int ans = c.size(), nxt = 0;
while (!clock(c.back(), c[nxt], c[nxt + 1])) nxt++;
give_answer(ans - nxt);
}
# | 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... |