Submission #463816

#	Time	Username	Problem	Language	Result	Execution time	Memory
463816		Mamedov	Triangles (CEOI18_tri)	C++17	100 / 100	23 ms	2140 KiB

tri

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "trilib.h"
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool cmpD(int p1, int p2) {
    return is_clockwise(1, p1, p2);
}
bool cmpU(int p1, int p2) {
    return !is_clockwise(1, p1, p2);
}

void Find_CH(vector<int> &v, int dr) {
    v.pb(1);
    int ptr = 2;
    int i = 3;
    for(int i = 3; i < (int)v.size(); ++i) {
        while((dr ^ is_clockwise(v[ptr - 1], v[ptr], v[i]))) {
            --ptr;
        }
        v[++ptr] = v[i];
    }
    while((int)v.size() > ptr + 1) v.pop_back();
}
void solve() {
    int n = get_n();
    vector<int>U, D;
    D.pb(1); D.pb(2);
    U.pb(1); U.pb(2);
    for(int i = 3; i <= n; ++i) {
        if(is_clockwise(1, 2, i)) {
            D.pb(i);
        }else {
            U.pb(i);
        }
    }
    sort(D.begin() + 2, D.end(), cmpD);
    Find_CH(D, 1);
    D.pop_back();
    reverse(D.begin(), D.end());
    D.pop_back();

    sort(U.begin() + 2, U.end(), cmpU);
    Find_CH(U, 0);
    reverse(U.begin(), U.end());
    U.pop_back();
    U.pop_back();

    while(D.size() && U.size()) {
        if(D.size() > 1 && is_clockwise(D[D.size() - 2], D[D.size() - 1], U.back())) D.pop_back();
        else if(U.size() > 1 && is_clockwise(D.back(), U[U.size() - 1], U[U.size() - 2])) U.pop_back();
        else break;
    }
    reverse(D.begin(), D.end());
    reverse(U.begin(), U.end());

    while(D.size() && U.size()) {
        if(U.size() > 1 && is_clockwise(U[U.size() - 2], U[U.size() - 1], D.back())) U.pop_back();
        else if(D.size() > 1 && is_clockwise(U.back(), D[D.size() - 1], D[D.size() - 2])) D.pop_back();
        else break;
    }
    give_answer(U.size() + D.size());
}
int main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void Find_CH(std::vector<int>&, int)':
tri.cpp:26:9: warning: unused variable 'i' [-Wunused-variable]
   26 |     int i = 3;
      |         ^

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