Submission #898277

#	Time	Username	Problem	Language	Result	Execution time	Memory
898277		math_rabbit_1028	Triangles (CEOI18_tri)	C++14	20 / 100	1 ms	512 KiB

tri

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

int n, origin;
vector<int> up, dn;

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

bool compare2(int i, int j) {
    return !is_clockwise(i, 1, j);
}

void solve() {

    n = get_n();

    for (int i = 3; i <= n; i++) {
        if (is_clockwise(1, 2, i)) dn.push_back(i);
        else up.push_back(i);
    }
    sort(up.begin(), up.end(), compare);
    sort(dn.begin(), dn.end(), compare2);

    stack<int> stk;
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    for (int i = 0; i < up.size(); i++) {
        int a = dq.back(); dq.pop_back();
        while (dq.size() >= 1 && is_clockwise(dq.back(), a, up[i])) {
            a = dq.back(); dq.pop_back();
        }
        dq.push_back(a);
        dq.push_back(up[i]);
    }
    dq.pop_front();
    dq.push_back(1);

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

    int st = dq.back();
    while (stk.size() > 2) {
        int v = stk.top();
        stk.pop();
        int a = dq.back(); dq.pop_back();
        while (dq.size() >= 1 && is_clockwise(dq.back(), a, v)) {
            a = dq.back(); dq.pop_back();
            st = dq.back();
        }
        dq.push_back(a);
        dq.push_back(v);
    }

    while (stk.size() > 0) stk.pop();
    while (dq.front() != st) {
        dq.push_back(dq.front());
        dq.pop_front();
    }
    stk.push(st); dq.pop_front();
    while (dq.size() > 0) {
        int v = dq.front();
        dq.pop_front();
        int a = stk.top(); stk.pop();
        while (stk.size() >= 1 && is_clockwise(stk.top(), a, v)) {
            a = stk.top(); stk.pop();
        }
        stk.push(a);
        stk.push(v);
    }

    give_answer(stk.size());

}

int main() {
    solve();
}

Compilation message (stderr)

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

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