Submission #898303

#	Time	Username	Problem	Language	Result	Execution time	Memory
898303		math_rabbit_1028	Triangles (CEOI18_tri)	C++14	75 / 100	26 ms	2312 KiB

tri

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

int n, ch[404040], cnt = 0;
vector<int> up, dn;

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(), [](int i, int j){ return is_clockwise(i, 1, j); });
    sort(dn.begin(), dn.end(), [](int i, int j){ return !is_clockwise(i, 1, j); });

    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]);
    }

    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();
        }
        dq.push_back(a);
        dq.push_back(v);
    }

    for (auto iter = dq.begin(); iter != dq.end(); iter++) ch[*iter] = 1;

    sort(up.begin(), up.end(), [](int i, int j){ return !is_clockwise(i, 2, j); });
    sort(dn.begin(), dn.end(), [](int i, int j){ return is_clockwise(i, 2, j); });

    while (stk.size() > 0) stk.pop();
    dq.clear();
    dq.push_back(2);
    dq.push_back(1);
    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(2);

    stk.push(2);
    stk.push(1);
    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]);
    }

    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();
        }
        dq.push_back(a);
        dq.push_back(v);
    }

    for (auto iter = dq.begin(); iter != dq.end(); iter++) cnt += ch[*iter];
    give_answer(cnt);
}

int main() {
    solve();
}

Compilation message (stderr)

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

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