Submission #898173

#	Time	Username	Problem	Language	Result	Execution time	Memory
898173		math_rabbit_1028	Triangles (CEOI18_tri)	C++14	20 / 100	3095 ms	428 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

int n, origin;
vector<int> arr;

bool compare(int i, int j) {
    return is_clockwise(i, origin, j);
}



void solve() {

    n = get_n();

    int k = 1, l = 2, t = 0;
    while (++t) {
        bool f = false;
        for (int i = 1; i <= n; i++) {
            if (i != k && i != l) {
                if (!is_clockwise(k, l, i)) {
                    f = true;
                    if (t % 2 == 1) k = i;
                    else l = i;
                    break;
                }
            }
        }
        if (!f) break;
    }

    origin = l;

    for (int i = 1; i <= n; i++) if (i != origin) arr.push_back(i);
    sort(arr.begin(), arr.end(), compare);
    assert(arr[0] == k);

    stack<int> stk;
    stk.push(origin);
    stk.push(arr[0]);
    for (int i = 1; i < arr.size(); i++) {
        int a = stk.top(); stk.pop();
        while (stk.size() >= 1 && is_clockwise(stk.top(), a, arr[i])) {
            a = stk.top(); stk.pop();
        }
        stk.push(a);
        stk.push(arr[i]);
    }

    give_answer(stk.size());

}

int main() {
    solve();
}

Compilation message (stderr)

tri.cpp: In function 'void solve()':
tri.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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