Submission #400997

#	Time	Username	Problem	Language	Result	Execution time	Memory
400997		KoD	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	208 KiB

tri

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

template <class T>
using Vec = std::vector<T>;

using ll = long long;

int main() {
    const int N = get_n();
    Vec<int> upper, lower;
    for (int i = 3; i <= N; ++i) {
        (is_clockwise(1, 2, i) ? lower : upper).push_back(i);
    }
    std::sort(upper.begin(), upper.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    std::sort(lower.begin(), lower.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    Vec<bool> is_upper(N);
    for (const auto x: upper) {
        is_upper[x] = true;
    }
    Vec<int> order;
    const auto add =[&](const int i) {
        while (order.size() >= 2 and is_clockwise(order[order.size() - 2], order[order.size() - 1], i)) {
            order.pop_back();
        }
        order.push_back(i);
    };
    if (upper.empty()) {
        add(1);
        for (const auto x: lower) {
            add(x);
        }
        add(2);
        give_answer(order.size());
        return 0;
    }
    if (lower.empty()) {
        add(1);
        add(2);
        for (const auto x: upper) {
            add(x);
        }
        give_answer(order.size());
        return 0;
    }
    add(1);
    add(2);
    for (const auto x: upper) {
        add(x);
    }
    order.erase(order.begin());
    add(1);
    for (const auto x: lower) {
        add(x);
    }
    order.erase(order.begin());
    add(2);
    int idx = (int) order.size() - 1;
    while (!is_upper[order[idx]]) {
        idx -= 1;
    }
    Vec<int> next;
    for (int i = idx + 2; i < (int) order.size(); ++i) {
        next.push_back(order[i]);
    }
    for (int i = 0; i < idx; ++i) {
        next.push_back(order[i]);
    }
    const auto p = order[idx];
    const auto q = order[idx + 1];
    order.clear();
    add(p);
    add(q);
    for (const auto x: next) {
        add(x);
    }
    give_answer((int) order.size());
    return 0;
}

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