Submission #572242

#	Time	Username	Problem	Language	Result	Execution time	Memory
572242		piOOE	Triangles (CEOI18_tri)	C++17	100 / 100	25 ms	2244 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 40000;
const ll infL = 3e18;

int n;

bool ask(int i, int j, int k) {
    return is_clockwise(i + 1, j + 1, k + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = get_n();
    vector<int> ord(n), side(n);
    //0 - left, 1 - right
    iota(all(ord), 0);
    for (int i = 2; i < n; ++i) {
        side[i] = ask(0, 1, i);
    }
    stable_sort(2 + all(ord), [&side](int i, int j) {
        if (side[i] != side[j]) {
            return side[i] < side[j];
        }
        return ask(0, i, j);
    });
    for (int i = 2; i < sz(ord); ++i) {
        if ((i == sz(ord) - 1 && side[ord[i]] == 0) || (i != sz(ord) - 1 && side[ord[i]] == 0 && side[ord[i + 1]] == 1)) {
            rotate(begin(ord) + 1, begin(ord) + 2, begin(ord) + i + 1);
            break;
        }
    }
//    for (int x : ord)
//        cout << x << " ";
//    cout << endl;
    deque<int> st;
    for (int i : ord) {
        while (sz(st) > 1 && !ask(st.end()[-2], st.back(), i)) {
            st.pop_back();
        }
        st.push_back(i);
    }
    while (sz(st) >= 3) {
        if (!is_clockwise(st.end()[-2] + 1, st.end()[-1] + 1, st[0] + 1)) {
            st.pop_back();
        } else if (!is_clockwise(st.end()[-1] + 1, st[0] + 1, st[1] + 1)) {
            st.pop_front();
        } else {
            break;
        }
    }
    cout << sz(st);
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25