Submission #539111

#	Time	Username	Problem	Language	Result	Execution time	Memory
539111		aniervs	Triangles (CEOI18_tri)	C++17	100 / 100	32 ms	2444 KiB

tri

#include<bits/stdc++.h>
#ifndef LOCAL
#include "trilib.h"
#endif
#define endl '\n' 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

using ll = long long;
using db = long double;
const int maxn = 2e5 + 5;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

#ifdef LOCAL
const vector<pair<int,int>> points = {{1, 1}, {4, 3}, {2, 2}, {1, 4}, {5, 1}, {3, 2}};
int get_n(){
    return points.size();
} 
long long cross(const pair<int,int> a, const pair<int,int> b){
    return a.first * b.second - a.second * b.first;
}
pair<int,int> operator -(const pair<int,int> &a, const pair<int,int> &b){
    return {a.first - b.first, a.second - b.second};
}
bool is_clockwise(int a, int b, int c){
    return cross(points[b-1] - points[a-1], points[c-1] - points[a-1]) < 0;
}
void give_answer(int s){
    cout << s << endl;
}
#endif

vector<int> arr[2];

void merge_sort(vector<int> &a, int l, int r){
    if(l >= r){
        return;
    }
    int mid = (l + r)>>1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    vector<int> c;
    merge(a.begin() + l, a.begin() + mid + 1, a.begin() + mid + 1, a.begin() + r + 1, back_inserter(c),  [&a](const int p, const int q){
        return !is_clockwise(a[0], p, q);
    });
    for(int i = l, j = 0; i <= r; i++, j++){
        a[i] = c[j];
    }
}

vector<int> compute_convex_hull(vector<int> a){
    if(a.size() <= 2)
        return a;
    merge_sort(a, 1, a.size() - 1);
    vector<int> h;

    for(auto p:a){
        while(h.size() > 1 and is_clockwise(h[h.size() - 2], h[h.size() - 1], p))
            h.pop_back();
        h.push_back(p);
    }

    return h;
}

vector<int> merge_convex(const vector<int> &a, const vector<int> &b){
    int n = a.size(), m = b.size();
    vector<int> c;

    int l1, l2, r1, r2;

    {
        // upper part
        int l = 0, r = 0;
        while(true){
            if(m > 1 and !is_clockwise(a[l], b[r], b[(r - 1 + m) % m])) r = (r - 1 + m) % m; 
            else if(n > 1 and is_clockwise(b[r], a[l], a[(l + 1)% n])) l = (l + 1) % n;
            else break;
        }

        l1 = l, r1 = r;
        
    }
    
    {
        // lower part
        int l = 0, r = 0;
        while(true){
            if(m > 1 and is_clockwise(a[l], b[r], b[(r + 1) % m])) r = (r + 1) % m;
            else if(n > 1 and!is_clockwise(b[r], a[l], a[(l - 1 + n) % n])) l = (l - 1 + n) % n;
            else break;
        }

        l2 = l, r2 = r;
    }  
    while(true){
        c.push_back(a[l1]);
        if(l1 == l2) break;
        l1 = (l1 + 1) % n;
    }
    while(true){
        c.push_back(b[r2]);
        if(r2 == r1) break;
        r2 = (r2 + 1) % m;
    }
    
    sort(all(c));
    c.erase(unique(all(c)), c.end());

    return c;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0); 

    int n = get_n();
    arr[0] = {1}, arr[1] = {2};
    for(int i = 3; i <= n; i++){
        arr[is_clockwise(1, 2, i)].push_back(i);
    }

    arr[0] = compute_convex_hull(arr[0]);
    arr[1] = compute_convex_hull(arr[1]);
    
    auto ans = merge_convex(arr[0], arr[1]);

    give_answer(ans.size());

    cerr << endl << "Running time: " << (double)clock()/CLOCKS_PER_SEC << " seconds."<< endl;

    return 0;
}

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