Submission #951190

#	Time	Username	Problem	Language	Result	Execution time	Memory
951190		glebustim	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	604 KiB

tri

#include "trilib.h"
//#include "trilib.c"
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

bool comp(int x, int y) {
    return is_clockwise(1, y, x);
}

int main() {
    int n = get_n();
    vi a, b;
    for (int i = 3; i <= n; ++i) {
        if (is_clockwise(1, 2, i))
            a.push_back(i);
        else
            b.push_back(i);
    }
    sort(all(a), comp);
    sort(all(b), comp);
    vi c = {1};
    for (int i: a)
        c.push_back(i);
    c.push_back(2);
    for (int i: b)
        c.push_back(i);
    vi st;
    for (int i: c) {
        while (st.size() > 1 && is_clockwise(st[(int)st.size() - 2], st.back(), i))
            st.pop_back();
        st.push_back(i);
    }
    for (int i: c) {
        while (st.size() > 1 && is_clockwise(st[(int)st.size() - 2], st.back(), i))
            st.pop_back();
        st.push_back(i);
    }
    vi cnt(n, 0);
    int ans = 0;
    for (int i: st) {
        ++cnt[i];
        if (cnt[i] == 2)
            ++ans;
    }
    give_answer(ans);
}

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